[DFS, BFS] 백준 2178번: 미로 탐색

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

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

x_lim, y_lim = map(int, input().split())

maze = []
for i in range(x_lim):
    r = input()
    maze.append(list(r))

q = [[0,0,1]] # x, y, walk
while q:
    cur = q.pop(0)
    x = cur[0]
    y = cur[1]
    walk = cur[2]

    if x == x_lim-1 and y == y_lim-1:
        print(walk)
        break

    if x >= 0 and x < x_lim and y >= 0 and y < y_lim and maze[x][y]=='1':
        maze[x][y] = '0'
        q.append([x+1, y, walk+1])
        q.append([x-1, y, walk+1])
        q.append([x, y-1, walk+1])
        q.append([x, y+1, walk+1])

비슷한 문제를 DFS문제로 푼 기억이 있어 생각없이 DFS로 풀다가 엄청 헤맸다.

이 문제는 BFS로 접근해야 풀이가 가능하다. 또한 단계별로 걸음 수를 증가시켜 주어야 하기 때문에

이 방법을 고민해보다가 리스트 q에 위치정보를 담을 때 걸음 수도 추가해 담기로 하였다.

그것이 위의 코드 walk에 해당하는 부분이다.

배운 점

- 지도를 볼 때 아래 처럼 축을 생각하고 진행하는 게 편하다.

2차원 리스트에 지도를 담게 되면

a[]에 해당하는 부분이 x이기 때문에 인덱스가 증가할수록 아래 행으로 넘어가고,

a[][]에 해당하는 부분이 y이기때문에 인덱스가 증가할수록 다음 열로 넘어가기 때문이다.