미로 탐색 역시 BFS를 통해 해결하는 문제이다. 가장 왼쪽 상단 위인 (1, 1) 좌표에서 시작하여 N x M 미로의 크기인 (N, M)까지 이동하는 최단 경로를 구해야 한다.
BFS는 특정 노드를 기준으로 너비 우선 탐색을 진행한다고 하였다. 여기서 노드를 좌표로 생각하고 탐색 방향을 동, 서, 남, 북으로 잡으면 최단 경로를 구할 수 있다.
문제는 동, 서, 남, 북 순서로 이동하는 조건 검사를 어떻게 진행하여 해결할 것인가?
이를 해결하기 위해 벡터 배열이라는 새로운 개념이 필요하다.
먼저 우리는 미로의 크기만큼 N x M 크기의 2차원 행렬을 선언하여 저장해야 한다.
# N x M 데이터 크기를 저장하는 2차원 행렬
A = [[0] * M for _ in range(N)]
# N x M 만큼 입력받아 2차원 행렬 저장
for i in range(N):
numbers = list(input())
for j in range(M):
A[i][j] = int(numbers[j])행렬 A의 인덱스가 (i, j)라고 한다면 행(row)은 i를 나타내고 열(column)은 j를 나타낸다.
여기서 중요한 포인트는 탐색을 진행할 때 i(행)는 위에서 아래로 갈수록 값이 증가하고, j(열)는 왼쪽에서 오른쪽으로 갈수록 값이 증가한다.
그래서 우리가 수학에서 생각하는 (x, y) 좌표가 코드에서는 반대로 뒤집어서 이동한다고 생각해야 한다.
예를 들어 (0, 1)은 동쪽(오른쪽)으로 1칸 이동한 것이다.
따라서 이를 녹여낸 벡터 배열인 dx, dy 코드는 다음과 같다.
# 동, 서, 남, 북 순위
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]동쪽으로 이동하는 것을 해석해보면 (dx[0], dy[0]) = (0, 1)과 같은 형태가 되는 것이다.
근데 사실 잘 생각해보면 이동방향의 우선순위가 항상 동, 남 쪽이 되므로 dx, dy 배열은 아래와 같이 수정해야 한다.
# 동, 남, 서, 북 순위
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]이제 큐에서 pop한 노드를 기준으로 동, 남, 서, 북 순서로 반복하며 이동할 수 있는 경로인 경우 큐에 push를 진행해주면 된다.
물론 미로에서 이동할 수 없는 좌표는 0으로 표시한 것과 동시에 이미 방문한 좌표인지, 그리고 마지막으로 행렬의 범위를 벗어난 좌표는 아닌지 검사하는 조건이 모두 들어가야 한다.
Python
따라서 파이썬 전체 코드는 아래와 같다.
import sys
input = sys.stdin.readline
from collections import deque
# 동, 남, 서, 북으로 이동하기 위한 벡터 배열
# dx와 dy를 위, 아래로 조합하여 봐야함
# e.g. (dx[0], dy[0]) = (0, 1)이 동쪽 이동을 의미함
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
queue = deque()
N, M = map(int, input().split())
# N x M 데이터 크기를 저장하는 2차원 행렬
A = [[0] * M for _ in range(N)]
# N x M 크기의 2차원 방문리스트
visited = [[False] * M for _ in range(N)]
# N x M 만큼 입력받아 2차원 행렬 저장
for i in range(N):
numbers = list(input())
for j in range(M):
A[i][j] = int(numbers[j])
def BFS(i, j):
# 큐에 시작 좌표를 push
queue.append((i, j))
visited[i][j] = True
# 큐가 비어있을때까지 반복
while queue:
# 현재 좌표노드를 pop
node = queue.popleft()
# 동, 남, 서, 북 순서로 반복
for k in range(4):
# 현재 노드에서 동, 서, 남, 북을 더해 이동할 위치의 좌표 생성
x = node[0] + dx[k]
y = node[1] + dy[k]
# 이동할 수 있는 좌표의 위치인지 검사
# x or y가 -1인 경우 행렬의 범위를 벗어난 좌표를 의미함
if x >= 0 and y >= 0 and x < N and y < M:
# 한번도 방문한 적이 없고, 이동할 수 있는 좌표인 경우(1로 표시된 지역인 경우)
if A[x][y] != 0 and not visited[x][y]:
visited[x][y] = True
# 이동할 좌표지역에 이동했다는 의미로 +1을 더함
A[x][y] = A[node[0]][node[1]] + 1
queue.append((x, y)) # 이동한 좌표를 큐에 push
BFS(0, 0)
print(A[N - 1][M - 1])Java
따라서 자바의 전체 문제풀이 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P_2178 {
// 동, 남, 서, 북을 탐색하기 위한 배열 선언
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static boolean[][] visited; // 미로 방문여부 체크를 위한 2차원 배열
static int[][] A; // 미로를 저장하기 위한 2차원 배열
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
// 값을 붙여서 입력받았으므로 substring(start_idx, end_idx - 1)을 통해 하나씩 저장
for (int j = 0; j < M; j++) {
A[i][j] = Integer.parseInt(line.substring(j, j + 1));
}
}
BFS(0, 0);
System.out.println(A[N - 1][M - 1]);
}
static void BFS(int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i, j}); // 시작 좌표를 push
visited[i][j] = true;
while (!queue.isEmpty()) {
// 현재 위치좌표의 노드를 꺼냄
int[] nowNode = queue.poll();
// 동, 남, 서, 북 기준으로 반복
for (int k = 0; k < 4; k++) {
// x, y는 반복문이 돌며 동, 남, 서, 북으로 이동한 좌표를 나타냄
int x = nowNode[0] + dx[k];
int y = nowNode[1] + dy[k];
// 미로 크기에 벗어나지 않고 이동할 수 있는 좌표이면서
if (x >= 0 && y >= 0 && x < N && y < M) {
// 0이 아니라서 이동할 수 있는 좌표이면서
// 아직 방문하지 않은 경우
if (A[x][y] != 0 && !visited[x][y]) {
visited[x][y] = true;
A[x][y] = A[nowNode[0]][nowNode[1]] + 1; // 이동할 좌표에 +1 더함
queue.add(new int[]{x, y}); // 이동한 좌표 push
}
}
}
}
}
}모든 조건이 들어맞으면 이동할 좌표에 +1을 더해가며 (N, M) 좌표까지 이동한 결과를 출력하면 최단경로의 수가 된다.
