[SWEA 5105][파이썬 S/W 문제해결 기본]. 6일차 - 미로의 거리

문제

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

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

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

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

13101
10101
10101
10101
10021

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

 

 

 

 

내 생각

최단거리를 구하는 문제이다. → BFS 

1. N과 미로 입력받기

2. 시작점인 2의 위치를 찾아 탐색을 시작한다.

for i in range(N):
        if 2 in maze[i]:
            sx, sy = i, maze[i].index(2)  #start_x, start_y
            break

3. BFS 함수
BFS는 queue를 사용한다. visited로 방문처리를 해야하지만, 이 문제에서는 최단 거리를 구하는 문제이므로, distance라는 명칭으로 방문처리와 거리합산을 동시에 진행한다.

자세한 코드설명은 주석에 있다. 

 

 

 

 

 

내 코드

def bfs(x, y):
    distance = [[0 for _ in range(N)] for _ in range(N)] #visited와 같은 역할 
    queue = [(x, y)] #시작지점을 큐에 삽입
    direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 상하좌우
    while queue: #큐가 비어있지 않다면
        x, y = queue.pop(0) #큐의 첫번째 원소를 반환
        if maze[x][y] == 0 or maze[x][y] == 2: #미로의 원소가 0이나 2이면(방문되지 않은 곳)
            maze[x][y] = 1 #해당 원소를 1로 만들어줘서 (방문처리)
            for dx, dy in direction: #상하좌우 이동시작
                nx, ny = x + dx, y + dy #위치 + 상하좌우 = 새로운 위치
                if 0 <= ny <= N-1 and 0 <= nx <= N-1: # 범위지정해주기 (중요)
                    if maze[nx][ny] == 0: # 새로운 위치(상하좌우)미로가 0이면 (방문되지 않은 곳)
                        distance[nx][ny] = distance[x][y] + 1 #미로가 0이면 갈 수 있는 경로(거리합산에 +1)
                        queue.append((nx, ny)) #큐에 위치를 넣어준다
                    elif maze[nx][ny] == 3: #미로가 3이면(도착지점)
                        return distance[x][y] 
    return 0

T = int(input())
for test_case in range(1, T+1):
    N = int(input()) #N입력
    maze = [list(map(int, list(input()))) for _ in range(N)] #미로입력 (N만큼)
    for i in range(N):
        if 2 in maze[i]: #시작점 2를 찾기
            sx, sy = i, maze[i].index(2) #i:숫자2 행의 인덱스, maze[i].index(2):숫자 2의 열 인덱스
            break
    print('#{} {}'.format(test_case, bfs(sx, sy)))