[PART2] 5-2(DFS/BFS): 미로 탈출

코뉴·2021년 1월 21일

BFS DFS 이코테

이코테: 문제풀이

목록 보기

17/28

💥이코테 실전문제 뽀개기💥

💻 5-2 미로 탈출

난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB

📌2021/01/21 작성 코드

from collections import deque

def bfs(graph, row, col):
    # 큐를 만들고, 시작 노드 큐에 삽입
    queue = deque()
    queue.append([row, col])
    # 방문 처리: (1, 1)부터 시작하므로 인덱스 고려해서 -1씩
    graph[row-1][col-1] = 0 # 0 으로 처리해준다
    # 큐가 빌 때까지 반복한다
    result = 0 # 몇 개의 칸을 거치는지
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        result += 1
        # print(v, end=' ')
        # 아직 방문하지 않은 원소들을 큐에 삽입한다
        # 최단거리이므로 우, 하로 전진해야 한다고 생각해
        # 우
        if 0 < col + 1 <= m and graph[row-1][col] == 1:
            queue.append([row, col+1])
            graph[row-1][col] = 0 # 방문 처리
            col += 1 # col 증가
        # 하
        if 0 < row + 1 <= n and graph[row][col-1] == 1:
            queue.append([row+1, col])
            graph[row][col-1] = 0 # 방문 처리
            row += 1 # row 증가
    return result

# 입력
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

# bfs 호출
print(bfs(graph, 1, 1))

💭 아이디어

왜 BFS로 실행해야 한다는 이유 없이 BFS로 실행한 ... 어딘가 치밀하지 못한 사고 과정😵

방문 처리를 현재 있는 graph 상에서 0으로 바꿔줌으로 처리했으며
(1,1)에서 (n,m)으로 탈출하는 게 목표이기 때문에 우, 하 방향만 고려했다.

귀찮았던 건 인덱스 변환! (1, 1)이 사실은 리스트의 [0][0]!

유의해야 할 점은, 우측으로 이동하거나 아래로 이동할 때 col 또는 row의 값을 변화시켜주지 않으면 계속 초기값(1, 1)이 들어가서 원하는 결과를 내지 못한다!
어떻게 알았냐면요 저도 알고싶지 않았습니다😏

🤓 문제 해설

이 문제는 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다.
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

그러므로 (1, 1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다.
특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. (153p. 그림 참고)

++ (아래 답안 예시 추가설명)
참고로 소스코드 상에서, 첫 번째 시작 위치는 다시 방문할 수 있도록 되어 첫 번째 시작 위치에 해당하는 값이 3으로 변경될 여지가 있다. 하지만 본 문제에서는 단순히 가장 오른쪽 아래 위치로 이동하는 것을 요구하고 있기 때문에, 본 소스코드는 정상적으로 답을 도출하는 간결한 정답 코드이다.

🤓 답안 예시

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))