백준276 백준 16946 c++ "벽 부수고 이동하기4" -[PlusUltraCode] https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [필자 사고] 벽 부수고 이동하기 1,2,3,4 중 시리즈 문제이다. 대부분의 벽 부수고 문제는 벽을 부순다음 BFS탐색을 시작해야 됬다. 이 문제 또한 이전과 같은 방식을 사용하게 되면 시간이 초과된다. 따라서 필자는 0으로 되어있는 칸을 미리 전처리 탐색을 해줘서 이동할 수 있는 칸의 값을 부여해 줬다. 그 다음 마지막에 1인 불록 상,하,좌,우만 검사하여 각각 더해줬다... 2024. 3. 13. 백준 14442 c++ "벽 부수고 이동하기 2" -[PlusUltraCode] https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [필자 사고] 이 문제는 BFS업그레이드 문제이다. 이 문제를 풀기 시작했따면 장애물이 있을 때 BFS탐색 문제를 많이들 풀어 봤을 것이다. 장애물 BFS에 더불어서 visited[][][] 3차원으로 작성하여 벽을 부술 수 있는 능력까지 체크해주면 쉽게 풀 수 있다. [소스 코드] #include #include #include #include using na.. 2024. 3. 12. 백준 17135 c++ "캐슬 디펜스" -[PlusUltraCode] https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net [필자 사고] 이 문제는 구현 문제이다. 난이도가 높은 문제이다. 필자는 처음에 궁수의 자리를 어떻게 배치해야 할까를 고민하다 조합을 이용하여 이 부분을 해결했다. 그 다음 적을 죽이는 경우를 생각해보자 적이 사정거리 안에 있으면 죽일 수 있다. 이 부분을 우선순위 큐에 넣어 가장 가까운 적부터 죽이고 거리가 같다면 왼쪽에 더 가까운 적부터 죽이는 형식으로 코드를 작성했다. 또한 궁수가 공격을 멈추었다면 적.. 2024. 3. 11. 백준 1600 c++ "말이 되고픈 원숭이" -[PlusUltraCode] https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [필자 사고] BFS() 탐색 문제이다. 이 문제의 특이한 점은 말의 능력을 사용할 수 있다는 점이다. 처음 필자는 문제를 풀 때 visted를 2차원 배열로 구현하고 문제를 풀었지만 우선순위큐가 너무 과도하게 많이 만들어진 결과 메모리 초과의 문제를 만들어냈다. 핵심은 visted를 3차원 배열로 구현해 우선순위 큐가 과도하게 만들어지는걸 방지해야 된다. [소스 코드] #incl.. 2024. 3. 8. 이전 1 ··· 52 53 54 55 56 57 58 ··· 69 다음