[SWEA] 5102. 노드의 거리 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

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

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

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다.

노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

 

< ❓ 생각 >

< 💻 코드 >

def check(S,G):
    q = []
    # (위치, 최소 이동 간선 개수)
    q.append((S,0))
    # 방문했는가 표시
    visited = [0]*(V+1)
    visited[S] = 1
    while q:
        c,num = q.pop(0)
        # 현재 노드에서 갈 수 있는 경로 찾기
        for i in range(1, V + 1):
            # 연결되어 있고 방문하지 않은 노드라면 방문
            if adj[c][i] and not visited[i]:
                # 도착했는가?
                if i == G:
                    return num+1
                q.append((i, num + 1))
                visited[i] = 1
    # 도착 못 함(S와 G가 연결되어 있지 않음)
    return 0

# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # V : 노드의 개수, E : 방향성이 없는 간선
    V,E = map(int,input().split())

    # 인접행렬 : 간선 연결 확인
    # 노드 번호 1~V번
    adj = [[0]*(V+1) for _ in range(V+1)]

    # E개의 간선의 양쪽 노드 번호
    for _ in range(E):
        a,b = map(int,input().split())
        # 양쪽 다 표시
        adj[a][b] = 1
        adj[b][a] = 1

    # 출발 노드, 도착 노드
    S,G = map(int,input().split())

    # 최소 이동 간선 개수
    result = check(S,G)

    print(f'#{tc} {result}')

< ❗ 느낀 점 >

bfs를 이제 완벽히 이해해서 사용 가능하다. 뿌듯