미로의 거리 Python(SW Expert Academy)

난이도 : D3

문제번호 : 5105

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

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

예시

입력	출력
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

---

2. 문제풀이

SW 아카데미 기초문제들을 많이 풀고있는데 미로문제들이 많이보인다. 이번에는 BFS를 이용하여 미로를 풀어보았다. (카테고리가 아무래도 그러다 보니)  한칸 지날때 도착할 수 있는 모든 경로를 큐에 담아서 하나씩 전진해 나가는 구조로 만들었다. 지나왔던 장소는 1로 바꾸어 이동하지 못하도록 변경하였다. 큐가 한번 비워질때마다 카운트를 증가시켰으며 목적지에 도달하면 현재 카운트를 반환한다. 모든 경로를 탐색했는데도 불구하고 원하는 목적지를 찾지 못했다면 0을 리턴한다.

---

3. 소스코드

# D3 5105 미로의 거리
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
def bfs():
    global queue
    count = 0
    # 큐가 빌때까지 반복한다.
    # 세컨드 큐까지 비어있다면 이동을 못하는것이므로 0을 리턴하게 된다.
    while queue:
        seceond_queue = []
        #큐가 빌때까지 반복
        while queue:
            #x, y 좌표를 꺼내서
            y,x = queue.pop()
            #상 하 좌우로 이동해보자
            for i, j in move:
                dy = y+i
                dx = x+j
                #맵을 벗어나지 않는다면 체크
                if 0 <= dy < N and 0 <= dx < N:
                    #통로라면 지나왔다고 표시하고 큐에 추가
                    if not map_list[dy][dx]:
                        map_list[dy][dx] = 1
                        seceond_queue.append((dy, dx))
                    #도착지라면 현재까지 쌓인 카운트를 리턴
                    if map_list[dy][dx] == 3:
                        return count
        #큐가 빌때까지 반복되었다면 카운트를 늘려준다.
        count += 1
        #세컨큐를 기본큐에 넣어준다.
        queue = seceond_queue
    #여기까지 왔다면 통로는 찾을 수 없다.
    return 0
 
for t in range(1, 1+int(input())):
    N = int(input())
    map_list = [list(map(int, list(input()))) for _ in range(N)]
    queue = []
    for i in range(N):
        for j in range(N):
            #2를 찾는다면 큐에 넣고 브레이크
            if map_list[i][j] == 2:
                queue.append((i, j))
                break
        #esle는 브레이크에 걸리지 않았을때만 동작한다.
        #못찾았다면 위로 올린다.
        else: continue
        #2를 찾았다면 더이상의 반복문은 필요가 없으므로 정지
        break
    #결과값을 출력한다.
    print('#{} {}'.format(t, bfs()))