미로 탐색 Python (BEAKJOON)

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

2178번: 미로 탐색

1. 문제 설명

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

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

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

2. 코드

항상 미로문제는 dfs를 구현하며 풀었습니다. 이 문제 또한 dfs를 활용하여 작성하여 예제를 풀었을 경우 예제 코드는 정답이 맞게 나왔지만 시간초과가 걸렸습니다... 중간에 거리가 결과값보다 길어지면 멈추는 방법을 쓰긴 했지만 큰 차이는 없던 것 같습니다.

조금 생각을 해보니 bfs로 구현하며 각 칸까지 가는 거리를 새롭게 저장한다면 시간이 훨씬 단축될 것을 알 수 있었습니다. 1인 칸을 4방향으로 검사하기만 하고 다시 돌아갈 필요가 없기 때문입니다...

결과적으로 bfs를 활용하여 통과를 했습니다. 이번 문제에서 또한 dfs와 bfs의 차이를 느낄 수 있었습니다. 상황에 맞는 방법을 찾는 것을 연습해야 할 것 같습니다.

 

아래가 작성한 코드입니다.

# 경계와 갈 수 있는 길을 확인한는 함수
def boundary(x,y):
    if x>=0 and x<M and y>=0 and y<N and maze[y][x]==1:
        return True
    return False
 
# 우, 좌, 하, 상
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
N, M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]
 
# 0,0 에서 시작
q = [[0, 0]]
while len(q):
    x, y = q.pop(0)
    # 현 위체에서 4방향으로 갈 수 있는지 검사
    for d in range(4):
        if boundary(x+dx[d], y+dy[d]):
            # 갈 수 있으면 +1을 해서 해당 칸에 저장
            maze[y+dy[d]][x+dx[d]] = maze[y][x] + 1
            q.append([x+dx[d], y+dy[d]])
# M,N에 있는 결과를 출력
print(maze[N-1][M-1])