[BFS] 백준 2178 문제풀이

말그대로 미로탐색 문제였다. 1,1에서 n,m까지 이동하는 경우의 수를 찾으면 된다. 

최소의 칸 수를 출력해야 하기 때문에 BFS를 사용하였다. 

from collections import deque


def bfs(v):
    queue.append((0, 0))

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while queue:
        x, y = queue.popleft()
        for i in range(4):  # 자식노드 큐에 추가하기 위함
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if visit[nx][ny] == False and matrix[nx][ny] == 1:
                    queue.append((nx, ny))
                    visit[nx][ny] = True
                    result[nx][ny] = result[x][y] + 1


n, m = map(int, input().split())
matrix = [list(map(int, input())) for _ in range(n)]
visit = [[False] * m for _ in range(n)]
queue = deque()
result = [[1] * m for _ in range(n)]
#print(matrix)
bfs(0)
print(result[ n- 1][m - 1])

 

bfs는 큐를 사용하기 때문에 deque 를 이용해주었다. 

탐색할 노드를 튜플로 저장하여 탐색할때 pop한다. 상하좌우를 전부 봐주어야 하므로 dx,dy를 만들고 for문을 4번 돌려 양옆,위아래중 갈 수 있는 길이 있다면 큐에 추가해준다. 그리고 우리는 칸 수를 세주어야 하기 때문에 result에 이동 전 칸 수 +1을 저장해준다. 

이러한식으로 끝까지 돌고 n-1,m-1 자리 칸 수를 출력해주면 된다. (배열은 0부터 시작하므로)