https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 단순 bfs문제 + 벽을 한번 부술 수 있다는 특징이 있는 문제이다. 주요 풀이는 다음과 같다. 3차원 배열을 선언하여 거리를 저장해주는데 벽을 부수고 이동하면 [x][y][0] 에 값을 저장해주고 벽을 안부수고 이동했다면 [x][y][1]에 값을 저장해준다. 다음 이동할 좌표가 맵의 범위 안이라면, 2가지 경우로 나눈다. 1. 벽을 만났는데, 뚫을 수 ..
https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 bfs 기본코드에서 약간의 응용이 필요하다. 우선 갈 수 있는 방향이 1.상 2.하 3.좌 4.우 5.좌상 6.우상 7.좌하 8.우하 9.제자리 로 총 9가지다. 그리고 벽이 1초에 한 줄씩 내려온다고 하였으므로, 1초마다 벽의 위치를 움직여줘야한다. 0,0에서 부터 for문을 시작하면 벽을 내리고, 내린 벽과 기존 벽을 구분하기 어려우므로 밑에서부터 for문을 시작하여 ..
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 기본적인 bfs문제에 약간의 테크닉을 요구하는 문제이다. 우선 C가 두개 주어지므로 그냥 먼저 나오는 C를 시작점이라고 치고, 늦게 나오는 C를 도착점이라 친다. 그리고 시작점을 큐에 넣고 bfs를 시작하는데, 큐의 맨 앞에 것을 가져와서 4가지 방향을 탐색하는 건 기존 bfs와 동일하다. 그러나 여기서 레이저의 특징을 이용해야한다! 레이저는 한 방향으로만 직진하므로, while문을 통해..
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 백준에서 bfs를 많이 연습했다면 크게 어렵지는 않았을 거라 생각한다. 문제를 풀이해보겠다! 우선, 백조의 위치를 vector에 저장한다. 그리고 물과 백조의 위치를 wq라는 큐에 저장해놓는다. 백조의 위치를 물의 위치와 같이 저장하는 이유는, 백조도 물에 떠있기 때문이다!! 만약 백조가 X에 둘러 쌓여져 있는 상황에 처할 경우, 다음 날이 되면 물의 영향으로 길이 생..
