[이코테] : DFS/BFS (미로 탈출)

<조건>

난이도 : 🔵🔵⚪️⚪️

풀이 시간 : 30분

시간 제한 : 1초

메모리 제한 : 128MB

📖 문제

A는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력조건

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

 

이 문제는 앞선 문제와 비슷한 문제였다. 하지만 최단거리로 그냥 가면 되기 때문에 BFS로 인접한 것들을 빠르게 가면 되지 않을까 생각하여 문제를 해결하고자 했다. 

 

우선 입력값이다.

from collections import deque
import sys

# 맵의 크기 입력
n, m = map(int, sys.stdin.readline().split())

# 2차원 리스트에 맵 정보 입력 받기
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

이와 같이 입력값을 먼저 받는다.

 

그리고 이때 사용할 deque에 대해서도 import 하여 진행하는 것도 필요하다.

 

이후 함수에서 사용할 방향을 정의한 뒤 함수를 구성해보자.

# 상하좌우 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

 

1. 초기화 및 큐에 시작점 추가
BFS는 큐를 사용한다. deque([(x, y)])는 시작점 (x, y)를 큐에 넣고 탐색을 시작한다는 뜻이다. 큐는 선입선출(FIFO) 원칙에 따라 먼저 들어온 요소를 먼저 처리한다. 미로에서는 graph 리스트에 이동 거리를 기록하는데, 시작점 (0, 0)의 거리를 1로 설정하고 시작한다.

2. 큐가 빌 때까지 반복하며 탐색
while queue:는 큐에 탐색할 노드가 남아 있는 동안 반복한다는 뜻이다. queue.popleft()로 큐의 맨 앞에서 현재 위치 (x, y)를 꺼낸다.

3. 인접 노드 탐색 및 최단 거리 갱신
for i in range(4):는 현재 위치 (x, y)의 상하좌우 네 방향을 모두 살펴본다는 뜻이다. nx, ny는 다음으로 갈 위치를 계산하는 것이다.

다음 위치 (nx, ny)가 유효한지 확인하는 조건문들이 중요하게 작용한다.

a. nx < 0 or ny <0 or nx >= n or ny >= m: 탐색할 때 맵의 범위가 나가지 않도록 확인한다.

 

b.graph[nx][ny] == 0: 벽(0)에 부딪히면 지나갈 수 없으므로 다음 방향을 본다.

c. graph[nx][ny] == 1: 아직 방문하지 않은 통로(1)를 발견하면 이리로 가면 된다. 이때 1인 부분을 계속 방문하면서 해야 하는 것은 노드의 갯수를 세야 하기 때문에 노드를 +1 하도록 한다. graph[nx][ny] = graph[x][y] + 1: 지금 온 곳까지의 거리(graph[x][y])에 1을 더해 다음 위치까지의 최단 거리를 기록한 뒤 queue.append((nx, ny)): 다음으로 탐색할 위치를 큐에 넣는다. 다시 반복하도록 한다. 

4. 결과 반환

모든 탐색이 끝나면 return graph[n-1][m-1]을 통해 도착점까지의 최단 거리를 반환한다. BFS는 시작점에서부터 한 칸씩 거리를 늘려가며 탐색하기 때문에, 도착점에 가장 먼저 도달하는 거리가 무조건 최단 거리가 된다.

 

def bfs(x, y):
    # 큐 초기화 및 시작 노드 방문 처리
    queue = deque([(x, y)])

    # 큐가 빌 때까지 반복하며 탐색
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 상하좌우로 지나갈 때 일어나면 안되는 일 (그렇다면 그냥 이어서 가도록)
            if nx < 0 or ny <0 or nx >= n 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] # 마지막 그래프까지 어떻게 도달했는지 거리 반환을 의미함.

 

 

<전체 코드>

from collections import deque
import sys

# 맵의 크기 입력
n, m = map(int, sys.stdin.readline().split())

# 2차원 리스트에 맵 정보 입력 받기
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

# 상하좌우 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    # 큐 초기화 및 시작 노드 방문 처리
    queue = deque([(x, y)])

    # 큐가 빌 때까지 반복하며 탐색
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 상하좌우로 지나갈 때 일어나면 안되는 일 (그렇다면 그냥 이어서 가도록)
            if nx < 0 or ny <0 or nx >= n 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] # 마지막 그래프까지 어떻게 도달했는지 거리 반환을 의미함.


print(bfs(0,0))