[SWEA][D3][#05105] 미로의 거리

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

NxN 크기의 미로에서 출발지 목적지가 주어진다.

이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오.

경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다.

다음은 5x5 미로의 예이다. 1은 벽, 0은 통로를 나타내며 미로 밖으로 벗어나서는 안된다.

13101 10101 10101 10101 10021

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 5개의 칸을 지나 도착할 수 있다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 5<=N<=100

0은 통로, 1은 벽, 2는 출발, 3은 도착이다.

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
5
13101
10101
10101
10101
10021
5
10031
10111
10101
10101
12001
5
00013
01110
21000
01111
00000

출력

#1 5
#2 5
#3 0

My Sol

def findIJ(n):
    global mat, N
    for i in range(N):
        for j in range(N):
            if mat[i][j] == n:
                return i, j

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    mat = [list(map(int, input())) for _ in range(N)]
    visited = []
    for lst in mat:
        visited.append(lst[::])
    ni, nj = findIJ(2)
    ti, tj = findIJ(3)

    Q = [(0, ni, nj)]
    first = -1
    back = 1
    ans = 0
    while first < back-1 and not ans:
        first += 1
        nt, ni, nj = Q[first]
        didj = [(-1,0),(1,0),(0,-1),(0,1)]

        for di,dj in didj:
            if 0<=ni+di<N and 0<=nj+dj<N:
                if ni+di==ti and nj+dj==tj:
                    ans = nt
                elif not visited[ni+di][nj+dj]:
                    if not mat[ni+di][nj+dj]:
                        visited[ni+di][nj+dj] = 1
                        Q.append((nt+1, ni+di, nj+dj))
                        back += 1
    print(f'#{tc} {ans}')

deque를 사용해도 됐지만, 직접 deque를 구현하여 풀었던 문제였다. BFS를 이용해 시작점부터 목표점까지 최소 이동으로 도달해야 한다.

지도 이내에서 경계처리를 하고, 탐색 좌표가 visited에 표시하지 않았던 좌표라면 이를 visited에 표시하고 Queue에 추가해준다. 시작점과 도착점의 좌표는 함수를 이용해 코드 중복 없이 계산하였으며, Queue에는 tuple 형식으로 어떤 좌표의 위치 정보와 시작점으로부터의 거리까지 저장되는데, Quque에 넣기 전에 탐색 좌표가 목적 좌표와 같다면 현재 좌표가 가지는 시작점으로부터의 거리에 1을 더해 출력한다.

결과

PASS