[SWEA] 1238. contact - 파이썬

 

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

SW Expert Academy

 

- 인접한 노드로 뻗어나가는 구조이므로, 너비우선 탐색(bfs)를 이용한다

- 사람이 최대 100명까지 있다고 해서, 사람번호를 인덱스로 하고, 그 사람이 연락을 받았을 때의 시작사람과의 거리가 얼마인지를 저장해두는 리스트를 만들고 시작했다.(contacted 변수에 할당. 거리를 저장해두는 용도와 이미 연락했는지 확인하는 두가지 용도로 사용)

- 가장 마지막에 연락을 받는 사람이 여러명일 수 있으므로, 노드를 이동할때 마다 시작노드와의 거리를 저장해두고, 최대 거리를 가진 사람들끼리 비교해서 출력해야 한다.

 

제출코드

for tc in range(1,11):
    N,S = map(int,input().split())
    lst = list(map(int,input().split()))
    adj = [[] for _ in range(101)]  # 인접 리스트(비상연락망) 만들기
    for i in range(N//2):
        a = lst[i*2]
        b = lst[i*2+1]
        adj[a].append(b)
    contacted = [0 for _ in range(101)]  # 이미 연락을 받은 사람들 표시할 곳

    contacted[S] = 1  # 시작점은 이미 연락받은 셈이므로 표시
    Q = [S]

    while Q:  # 연락 전인 사람들이 남아 있으면 탐색을 계속해야하므로 반복
        now = Q.pop(0)

        for next in adj[now]:
            if contacted[next] == 0:
                contacted[next] = contacted[now] + 1
                Q.append(next)

    for ans in range(100,-1,-1):  # 사람 번호를 뒤부터 순회하며 max값을 만나면 출력 후 break
        if contacted[ans] == max(contacted):
            print(f'#{tc}',ans)
            break

풀이과정