[파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리 Python (SW Expert Academy)

출처 : https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

1. 문제 설명

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

2. 코드

큐를 이용하여 문제를 풀었습니다. 또한 거리를 저장하는 배열을 하나 만들어 끝점까지의 거리 정보를 저장하였습니다.

 

아래가 작성한 코드입니다.

# 경계와 벽을 확인하는 함수
def boundary(x, y):
    if x<0 or y<0 or x>N-1 or y>N-1 or maze[y][x] == 1:
        return False
    return True
 
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    maze = [list(map(int, input())) for _ in range(N)]
    # 출발점부터 거리를 저장할 배열
    distance = [[0 for _ in range(N)] for _ in range(N)]
    # 우 좌 하 상
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
 
    # 시작점과 끝점을 찾아냄
    for j in range(N):
        for i in range(N):
            if maze[j][i] == 3:
                start_x, start_y = i, j
            elif maze[j][i] == 2:
                end_x, end_y = i, j
    result = 0
    q = [[start_x, start_y]]
    maze[start_y][start_x] = 1
    # bfs
    while len(q):
        x, y = q.pop(0)
        # 끝점에 도착하면 결과에 저장하고 종료
        if x == end_x and y == end_y:
            result = distance[y][x] - 1
            break
        # 현재 큐에서 4방향 검사
        for d in range(4):
            if boundary(x+dx[d], y+dy[d]):
                # 지나간 의미로 벽을 세움
                maze[y+dy[d]][x+dx[d]] = 1
                # 거리 저장
                distance[y+dy[d]][x+dx[d]] = distance[y][x] + 1
                q.append([x+dx[d], y+dy[d]])
    print('#{} {}'.format(tc, result))