SWEA 5105 - 미로의 거리

 

 

처음 든 생각

- BFS로 거리에 따라 하나씩 탐색을 해야겠다.

- 3인 점을 처음 발견하면 그 때가 최소 거리가 될테니깐 함수를 중단하면 되겠다.

- 방문한 사실 확인 + 출발점에서의 거리를 한 번에 계산해야겠다.

 

나의 코드

T = int(input())
from collections import deque
for test_case in range(1, T + 1):
    N = int(input())
    a= [[] for _ in range(N)]

    starting =[0,0]
    for i in range(N):
        a[i] = list(map(int, list(input())))
        if 2 in a[i]:
            starting[0] = i
            starting[1] = a[i].index(2)
    q = deque()
    q.append(starting)
    a[starting[0]][starting[1]] = 4
    
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    found = False
    result = 0
    while q and found != True:
        temp = q.popleft()
        for i in range(4):
            nx = temp[1] + dx[i]
            ny = temp[0] + dy[i]
            if nx<N and nx>=0 and ny<N and ny>=0:
                if a[ny][nx] == 3:
                    found = True
                    result = a[temp[0]][temp[1]] - a[starting[0]][starting[1]]
                    break
                elif a[ny][nx] == 0:
                    q.append([ny, nx])
                    a[ny][nx] = a[temp[0]][temp[1]] + 1 
    if found:
        print(f"#{test_case} {result}")
    else:
        print(f"#{test_case} 0")

 

먼저 전체 미로를 2차원 리스트로 표현하고 시작점을 구한다.

 

그 다음 BFS를 하기 위해 큐를 선언한다. 큐를 통해서 거리에 따라 노드를 계속 추가하는 방식으로 탐색을 할 예정이다.

ex 거리가 1인 노드들 먼저 큐 안에 다 넣고 그다음 popleft해서 탐색

 

시작점을 4라고 표시했다. 0,1,2,3은 이미 각각의 숫자가 의미를 가지고 있었기에 4부터 거리를 측정하기로 했다. 4 이상이면 이미 방문했다는 뜻이고 그에따라 거리를 하나씩 증가시켜주면서 계산을 하면 된다. 

 

그 다음부터는 본격적인 BFS 알고리즘이다.

found라는 플래그와 큐를 동시에 고려하여 반복문을 돌도록 설계하였고, 하나씩 노드를 popleft하면서 상하좌우의 노드들을 탐색한다.

만약 노드의 값이 0이라면 아직 방문하지 않았다는 뜻이기에 큐에 해당 노드를 추가해주고 이전 노드보다 거리가 1 늘어난 것이므로 값을 변경해준다.

만약 노드의 값이 3이라면 목표하는 노드에 도달한 것이므로 플래그를 True로 바꿔주고 지금까지 지나간 노드의 개수를 계산해준다.

 

그 외의 경우 (1,2, 4,5...)는 이미 방문했거나 방문할 수 없는 노드이기 때문에 추가적으로 고려할 사항이 없다.

 

결과는 플래그에 따라 출력해주면 된다.

---

BFS를 거의 처음으로 혼자 풀었던 것 같다. 첫 제출에 바로 pass해서 기분이 진짜진짜 좋았다.

 

어떤 식으로 반복문을 설계해야할지 어떤 걸 검사해야할지 큐를 어떻게 활용해야할지 감을 잡기에 아주 좋은 문제였다.