[백준] 2178번: 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

이 문제는 bfs최단 경로를 구하는 문제였다. 그 동안은 그래프 문제를 대부분 dfs를 먼저 적용하고 익숙하게 사용하였는데 이번 문제는 dfs로 구현할 경우 가지치기를 많이 번거롭게 많이하지 않는 이상은 구현이 거의 불가능하다. 그러므로 bfs를 연습할 겸 bfs로 구현하였다.

이 문제를 그래프의 기초를 더 다지기 위해 bfs문제로 양방향 관련 문제를 풀어봐야겠다.

 

 

n,m = map(int,input().split())
min = n*m
arr = []
for i in range(n):
    arr.append(list(map(int,input())))

visited = [[0 for i in range(m)] for j in range(n)]

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

q = [(0,0)]
visited[0][0] = 1

while q:
    x, y = q.pop(0)

    if x == n-1 and y == m-1:
        print(visited[x][y])
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0<= ny < m:
            if arr[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] +1
                q.append((nx,ny))