백준 2178번 파이썬

문제 링크

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

시간 제한 / 메모리 제한

1 초

192 MB

 

문제

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

출력

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

예제 입력

4 6
101111
101010
101011
111011

예제 출력

15

 

문제 풀이를 위해 생각한 것

1. 최단거리 문제이다. BFS를 활용할 수 있다.
2. 이동하며 미로의 각 지점을 시작지점부터의 최소 거리로 갱신하는 방법이 있고, (x, y, d)의 튜플로 구성하는 방법이 있다.
3. 본인은 보드를 직접 갱신하는 방법이 더욱 편리해서 보드를 갱신했다.

 

사용한 자료구조 / 알고리즘

2차원 배열, 큐 / BFS.

최단거리 문제를 풀 때는 시작 지점부터 한 depth씩 탐색하는 BFS의 depth 자체가 최단거리임을 활용할 수 있다.

 

풀이 코드

from collections import deque

n, m = map(int, input().split())
board = [list(map(int, input())) for _ in range(n)]
chk = [[False for _ in range(m)] for _ in range(n)]

dx = (1, -1, 0, 0)
dy = (0, 0, 1, -1)

q = deque()
q.append((0, 0))
chk[0][0] = True

while q:
    x, y = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1 and not chk[nx][ny]:
            board[nx][ny] = board[x][y] + 1
            chk[nx][ny] == True
            q.append((nx, ny))

print(board[n-1][m-1])

 

시간 복잡도 분석

O(NM).

방문한 지점은 재방문하지 않음으로 최대 N*M개의 지점을 방문한다. 따라서 시간 복잡도는 O(NM)이다.

*수정사항

N, M <= 100이므로, 최악의 상황에서 N과 M이 같다. 따라서 O(N^2)의 시간 복잡도를 가진다.

 

문제에서 중요한 부분

기본 길찾기 문제인데, 동서남북을 튜플로 미리 저장해놓고 반복문을 사용하는 것이 더욱 간결하게 코드를 작성하는 방법이다.