SWE(5102)_노드의거리

작성일 | In

SWE 5102 - 노드의 거리

  • V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다.

  • 주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오

  • 첫 줄 - 테스트 케이스의 개수
  • 다음 줄 : V와 E
  • E개의 줄에 걸쳐 간선의 양쪽 노드 번호가 주어진다

  • E개의 줄 이후에는 출발 노드와 도착 노드 G가 주어진다

  • 미로에서 그래프로만 변했을 뿐, 맥락을 동일하다.
  • 이 문제는 방향성이 없으므로 MyMap 좌표 안에 [start][end]와 [end][start] 두 곳 모두 경로를 찍어야 한다.
def BFS(start_node):
    global result
    Q.append(start_node)
    visited[start_node] = 1

    while Q:
        start_node = Q.pop(0)
        for next_node in range(1, v+1):
            if MyMap[start_node][next_node] and not visited[next_node]:
                Q.append(next_node)
                visited[next_node] = 1
                distance[next_node] = distance[start_node]+1
                if next_node == end_node:
                    result = distance[next_node]
                    return
    return  # 간선이 연결되지 않은 경우


TC = int(input())
for tc in range(1, TC+1):
    v, e = map(int, input().split())
    MyMap = [[0]*(v+1) for _ in range(v+1)]  # 계산의 편의를 위해, 앞 뒤로 0을 하나씩 더
    visited = [0] * (v+1)
    distance = [0] * (v+1)
    # 간선표시
    for i in range(e):
        start, end = map(int, input().split())
        MyMap[start][end] = 1
        MyMap[end][start] = 1
    #시작노드, 도착노드
    start_node, end_node = map(int, input().split())

    Q = []
    result = 0
    BFS(start_node)
    print(f'#{tc} {result}')

참고자료 [SWexperacademy]https://swexpertacademy.com [참고블로그]https://tothefullest08.github.io/algorithm/2019/03/09/4_5102_%EB%85%B8%EB%93%9C%EC%9D%98%EA%B1%B0%EB%A6%AC/

0%