SWEA - 미로의 거리 (5105) [Python]

 문제

 

- 기존에 풀었던 미로 문제와 흡사하지만 이동한 최소거리를 계산하는 문제이다. 이동 가능 위치는 0, 벽은 1, 출발점은 2, 목적지는 3이다. 

 

 

 

 문제 상황

 

- 기존에는 목적지 도착이 가능한지 여부였지만 이번에는 최소 거리다. 그냥 거리가 아니라 최소거리이므로 조건을 잘 설정해야한다.

 

 

 

 해결 전략

 

- 재귀를 이용한 풀이에 문제가 있어 큐를 이용해 다시 풀었다. distance 배열을 만들어 큐가 돌때마다 (해당 위치 +1) 값을 저장해 출발점(2)에서 부터의 거리를 계산하였다.

 

- visited 항목을 통해 이미 도착한 위치를 파악하고 변수 하나를 추가해 이동한 거리를 파악한다. 

 

 

 

 코드

 

from collections import deque
def BFS(x, y):
    # BFS를 위한 큐
    queue = deque([(x,y)])
    # 시작 위치에서는 거리가 0
    distance[x][y] = 0
    # 상하우좌 확인
    dx,dy = [-1,1,0,0], [0,0,1,-1]
    # 큐에 자료가 있는 동안 순회
    while queue:
        row, col = queue.popleft()
        for i in range(4):
            xx, yy = row + dx[i], col + dy[i]
            # 상하좌우가 범위 안에 있으면서 아직 방문한 적이 없을 때
            if 0<=xx<N and 0<=yy<N and distance[xx][yy] == -1:
                # 벽(1)이 아니라면 distance를 갱신해주고 큐에 넣어준다.
                if maze[xx][yy] == 0:
                    distance[xx][yy] = distance[row][col] + 1
                    queue.append((xx,yy))
                elif maze[xx][yy] == 3:
                    distance[xx][yy] = distance[row][col]
                    return
 
# testcase 입력
T = int(input())
for idx in range(T):
    # 미로의 한 변의 길이를 입력받는다.
    N = int(input())
    # 미로를 입력받는다.
    maze = [list(map(int,list(input()))) for _ in range(N)]
    # 방문 여부를 확인하는 리스트
    distance = [[-1 for _ in range(N)] for i in range(N)]
    # 출발지 찾기
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:
                BFS(i, j)
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 3:
                if distance[i][j] == -1 :
                    print(f"#{idx+1} 0")
                else:
                    print(f"#{idx+1} {distance[i][j]}")
               

 

 

 해설

 

- BFS는 큐, DFS는 스택으로 구현하는 것이 가장 편하다. 재귀로 다시 풀어볼 필요가 있다.

 

 

 

 새로 학습한 것 & 실수 

 

- 리스트의 합으로 연결 가능하다. ([1]+[2] = [1,2])

 

- 함수가 호출되기 전에 정의된 변수는 함수 안에서도 사용 가능하다.(N, distance)

 

 

출처 - https://swexpertacademy.com/main/