[백준] 2178번 미로 탐색

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

내 코드

def bfs(miro, y, x):
    queue = [(y, x)]

    while queue:
        ny, nx = queue.pop(0)
        num = miro[ny][nx]

        # 상하좌우 검사
        if 0 <= nx < M and 0 <= ny - 1 < N and miro[ny - 1][nx] == 1:
            miro[ny - 1][nx] = num + 1
            queue.append((ny - 1, nx))
        if 0 <= nx < M and 0 <= ny + 1 < N and miro[ny + 1][nx] == 1:
            miro[ny + 1][nx] = num + 1
            queue.append((ny + 1, nx))
        if 0 <= nx - 1 < M and 0 <= ny < N and miro[ny][nx - 1] == 1:
            miro[ny][nx - 1] = num + 1
            queue.append((ny, nx - 1))
        if 0 <= nx + 1 < M and 0 <= ny < N and miro[ny][nx + 1] == 1:
            miro[ny][nx + 1] = num + 1
            queue.append((ny, nx + 1))

N, M = map(int, input().split(' '))

miro = []

# 미로 받기
for i in range(N):
    row = list(map(int, input()))
    miro.append(row)

bfs(miro, 0, 0)

print(miro[N - 1][M - 1])

chatGPT

코드가 잘 작성되어 있습니다! BFS를 사용해 최단 경로를 찾는 구조는 올바르지만, 성능 개선과 코드 가독성을 높일 수 있는 몇 가지 제안을 드립니다.

개선 사항

1. deque 사용: 현재 queue.pop(0)을 사용하고 있는데, 이는 리스트의 첫 요소를 제거하면서 시간 복잡도가 O(N)입니다. collections.deque를 사용하여 O(1)로 popleft()를 호출하면 성능이 개선됩니다.
2. from collections import deque
3. 이동 방향 배열화: 상하좌우 이동을 각각 조건문으로 처리하는 대신, 방향을 배열로 정의하면 코드가 더 간결해집니다. 예를 들어, dy와 dx 배열을 사용해 반복문으로 처리할 수 있습니다.
4. directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
5. 미로 범위 체크 단순화: 이동하려는 좌표가 미로의 범위를 벗어나는지 체크할 때, 네 방향을 각각 따로 조건문으로 처리하기보다, 미로 범위 내에 있는지 한 번에 체크하면 코드가 더 단순해집니다.

개선된 코드

위 개선 사항을 반영한 코드는 다음과 같습니다.

from collections import deque
import sys

# input = sys.stdin.readline

def bfs(miro, start_y, start_x):
    queue = deque([(start_y, start_x)])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        y, x = queue.popleft()
        num = miro[y][x]

        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and miro[ny][nx] == 1:
                miro[ny][nx] = num + 1
                queue.append((ny, nx))

N, M = map(int, input().split())
miro = [list(map(int, input().strip())) for _ in range(N)]

bfs(miro, 0, 0)
print(miro[N - 1][M - 1])

설명

1. deque와 popleft()를 사용하여 큐에서 요소를 효율적으로 제거하도록 개선했습니다.
2. directions 배열을 사용해 상하좌우 이동을 반복문으로 처리하여 코드 중복을 줄였습니다.
3. input().strip()을 통해 입력 줄을 처리하여 줄 간격을 맞추는 데 더 안전하도록 했습니다.

내 생각

1. queue에서 deque를 사용하자.
2. 이동 방향을 배열에 넣어서 반복문을 돌리자.
3. 범위 체크할때 각각 따로 하지말고 배열에 넣을걸 꺼내서 반복문을 사용하자.
4. miro를 input() 으로 받을때 [] 내에서 한 번에 받는걸 외우자.
   • miro = [list(map(int, input().strip())) for _ in range(N)]