BFS : 미로탈출

문제설명

• 동빈이는 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

내가짠코드

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

flag = True  # left first if True(n>m), else down first(n<m)

if n < m:
    flag = False

i, j = 0, 0  # initial position\
cnt = 0

def func(i, j, cnt):
    print("HEY", i, j)
    if graph[i][j] == 1:
        graph[i][j] = True
        cnt += 1
        if flag == True:
            if i < m:
                result = func(i + 1, j, cnt)
                if result == False:
                    if j < n:
                        func(i, j + 1, cnt)
            else:
                func(i, j + 1, cnt)
        else:
            print("INIT", i, j, n, m)
            if j < n:
                result = func(i, j+1, cnt)
                print(i, j, result)
                if result == False:
                    if i < m:
                        func(i+1, j, cnt)
            else:
                func(i + 1, j, cnt)
        return True
    else:
        return False
func(i, j, cnt)

bfs를 활용해서 다시 짠 코드

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]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        if x == n - 1 and y == m - 1:
            return graph[x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx > n-1 or ny > m-1:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1

print(bfs(0,0)) # 10

정답코드

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]

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))

해설

이 문제에서는 n-1, m-1에 도달하면 바로 종료를 시키도록 while 루프 안에 조건문을 걸어 줄 수 있다. 최악의 경우 이 조건문을 수행하는 것은 비용이 되지만, 빠르게 목적지에 도달한다면 불필요한 연산을 피할 수도 있다. 최대한 불필요한 연산을 피하기 위해서는 아래 로직을 추가할 수 있다.
n이 m보다 작다면, 위 아래를 먼저 방문하도록 dx = [-1, 1, 0, 0], dy = [0, 0,-1, 1]
n이 m보다 크다면, 좌 우를 먼저 방문하도록 dx = [0, 0, -1, 1], dy = [-1, 1, 0, 0] 할 수 있을 것이다.