[bfs/백준] 2178번 : 미로 탐색

- 문제 : https://www.acmicpc.net/problem/2178

 

문제 이해

- 기본적인 bfs 문제이다.

- 왼쪽 끝에서 시작해 오른쪽 아래 끝까지 이동할 때 지나는 최소의 칸 수를 구하면 된다. 

 

풀이 로직

- 과정은 기본 bfs로 진행하면 된다. 

- 주어지는 행렬(matirx)과 방문여부를 확인하는 행렬(visit)을 따로 두어도 되지만, 이 때는 주어진 행렬로 탐색하면서 이전 노드의 값 + 1을 하면서 matrix가 visit 역할도 할 수 있게 했다. 

- 주의해야할 점은 행렬의 원소들 사이에 띄어쓰기가 없다는 것이다. 그래서 map(int, input().split())이 아닌 map(int, input())으로 입력해야한다. 

- 이동하면서 matrix[-1][-1]에 도착하지 못할 수도 있을거라 생각했는데, 아래 풀이가 정답인 걸 보면 일단 출발하면 목적지에 도착하는 방식인 것 같다. 

- 그래서 matrix[-1][-1]에 무조건 도착하므로 해당 행렬값을 출력하면 된다. 

 

정답 풀이

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input())))
    
queue = [[0, 0]]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
while queue:
    x, y = queue.pop(0)
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])
                
print(matrix[-1][-1])