[SWEA] 5102. 노드의 거리

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZmeHlF68SDHBIPN

SW Expert Academy

 

나의 방식

먼저 풀이에 앞서, 바킹독의 실전 알고리즘 강의를 들으면 도움이 되니까 문제가 풀기 어렵다면 꼭 듣는 것을 추천한다. 

https://www.youtube.com/watch?v=ftOmGdm95XI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=10

 

이 문제는 BFS(Breadth First Search)를 이용하는 문제로, 영상 내 미로 탐색 문제랑 매커니즘이 똑같다는 걸 알 수 있다. 

영상 내에서 언급한 주의할 점에 유의하자. 코드를 짜기 전에 나도 영상 내 언급된 모든 문제점을 실수했다.... 

 

기본적인 매커니즘은 

1. 시작점을 큐에 넣는다.
2. 큐에서 값을 빼내고 그 값과 인접한 점들을 방문 표시 후, 다시 큐에 넣는다.
3. 큐가 전부 빌 때까지 과정을 반복한다. 

T = int(input())

for test_case in range(1, T + 1):
    v, e = map(int, input().split())
    
    graph = [[0] * (v + 1) for _ in range(v + 1)]
    
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a][b] = 1
        graph[b][a] = 1

    start, end = map(int, input().split())

    visited = [False] * (v + 1)
    found = False 
    queue = [start]
    distance = [0] * (v + 1)

    while queue:
        node = queue.pop(0)

        if node == end:
            print(f'#{test_case}', distance[node])
            found = True
            break

        for i in range(1, v + 1):
            if graph[node][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)
                distance[i] = distance[node] + 1
    if not found:
        print(f'#{test_case} 0')

 

처음 내가 해결한 방식이다. 행렬을 통해 두 node 간 edge 가 있음을 표시했다. 

또한 visited 배열로 방문 여부를 표시하고 distance 배열로 거리를 측정했으며, found를 통해 목적지를 찾았는지 여부를 확인했다.

while queue:
    node = queue.pop(0)

    if node == end:
        print(f'#{test_case}', distance[node])
        found = True
        break

    for i in range(1, v + 1):
        if graph[node][i] == 1 and not visited[i]:
            visited[i] = True
            queue.append(i)
            distance[i] = distance[node] + 1
if not found:
    print(f'#{test_case} 0')

• 큐에서 노드를 하나 가져오고 목적지(end)인지 여부를 확인한다. 
  • 목적지가 맞다면 print()로 값을 리턴한다.
• 목적지가 아니라면, for loop를 통해 해당 노드와 인접한 노드 중 방문한 적이 없는(visited[i] = False) 노드를 큐에 추가한다.
  • 방문 표시를 여기서 꼭 해줘야 한다 (중복 요청 방지 위해)
  • distance는 distance[node] 값에서 + 1 된 값이다. 

 

이 상태에서도 코드가 잘 작동하지만, 너무 불필요한 List가 많고 found 같은 변수도 제거할 수 있을 거 같아 코드를 개선해보았다.

T = int(input())

for test_case in range(1, T + 1):
    v, e = map(int, input().split())

    graph = [[0] * (v + 1) for _ in range(v + 1)]
    
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a][b] = 1
        graph[b][a] = 1

    start, end = map(int, input().split())

    distance = [-1] * (v + 1)
    distance[start] = 0
    queue = [start]

    while queue:
        node = queue.pop(0)

        if node == end:
            print(f'#{test_case} {distance[node]}')
            break

        for i in range(1, v + 1):
            if graph[node][i] == 1 and distance[i] == -1:
                distance[i] = distance[node] + 1
                queue.append(i)
    else:  
        print(f'#{test_case} 0')

• visited[] 대신 distance[] 의 값이 -1 인지를 통해 방문 여부를 계산했다.
• found 라는 변수를 사용하는 대신 if 문 내에서 break 가 없으면 else 문으로 통하게 설정했다. 

 

더 나은 해결책이 있으면 공유 부탁드립니다.