[#2178] 미로 탐색

문제

#2178 미로 탐색
Silver1
적용 알고리즘: BFS 알고리즘

---

풀이 방법

• BFS 알고리즘 사용(DFS는 시간초과)
• 미로의 경로의 숫자(1)자체를 해당 칸까지 이동한 거리라고 생각하고 저장
• x, y한 쌍을 deque 자료의 한 쌍으로 생각
• 좌표가 board의 범위를 벗어나는지 확인
• visited로 방문한 곳을 저장
• 특정 칸에 도달했을 때, 상하좌우의 진행여부를 check

코드 흐름

1. deque 생성 후 처음 좌표 저장
2. deque에서 좌표를 하나 꺼내서, 해당 위치에서 상하좌우 방향의 진행 가능 경로를 확인하고, 경로의 값을 갱신, 만약 진행 가능한 경로면 이를 deque에 추가
3. deque에 저장된 모든 좌표에 대해서 2번 과정을 수행
4. deque에 남아있는 좌표가 없다면, 이는 탐색을 완료한 것. 마지막 좌표의 값을 출력

코드

from collections import deque


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

visited = [[False] * m for _ in range(n)]

# 상, 하, 우, 좌
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

path = deque()      # iterable 에러 방지 위해 우선 선언
path.append((0, 0))
visited[0][0] = True

while (path):
    x, y = path.popleft()
    for i in range(4):  # 각 방향에 대해서
        nx, ny = x + dx[i], y + dy[i]
        
        # board의 범위를 벗어나는지 확인
        if (0 <= nx < m and 0 <= ny < n):
            # 미로의 진행가능 경로인지, 미방문 경로인지 확인
            if (graph[ny][nx] == 1 and visited[ny][nx] == False):
                graph[ny][nx] = graph[y][x] + 1     # 해당 점 까지 오는데 소요된 거리 + 1
                visited[ny][nx] = True      # 방문 처리
                path.append((nx, ny))       # 진행 가능한 경로이므로 deque에 추가

for i in range(n):
    for j in range(m):
        print(graph[i][j], end=" ")
    print()

print(graph[n][m])

체감 난이도: 4.6/5
이미 DFS으로 하면 시간초과가 난다는 소식을 듣고(…) BFS로 해결했다. BFS는 항상 최단 거리를 보장하기 때문?에 그렇다고 한다. 미로찾기 등 최단거리를 구하는 문제에서는 BFS를 더 많이 활용한다고 한다. 결과 그래프를 출력해보니 이해가 더 잘되었던거 같다. 기회가 되면 DFS를 사용해서도 풀어봐야겠다.

---

[문제풀이 팁]

1. deque에서 좌표 꺼내기
deque 자료구조에 deque([0, 0])을 저장하고 각각의 좌표를 x, y로 뽑기 위해 popleft를 했는데 iterator 에러가 발생하였다. 이는 deque의 원소의 개수가 1개이기 때문에 y에 할당할 값이 없어서 에러가 나는 것이다. 이 경우 deque()를 우선 선언해준 뒤 append로 한 쌍의 좌표를 넣으면 해결된다.

# 잘못된 예시 -> iterator error 발생
path = deque([0, 0])
x, y = path.popleft()   # error

# 올바른 예시
path = deque()          # deque를 우선 선언
path.append([0, 0])
x, y = path.popleft()   # 정상 작동

2. 문자열 숫자를 리스트에 각각의 숫자로 쪼개기
map(), list() 함수 사용

temp = list(map(int, input()))