[Python, 파이썬] SWEA 1238. [S/W 문제해결 기본] 10일차 - Contact

비상연락망과 연락을 시작하는 당번에 대한 정보가 주어질 때,

가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 문제.

 

 

한 번 연락을 받은 사람에게 다시 연락을 하진 않고,

3, 6, 11, 22번과 같이 연락을 받을 수 없는 사람도 존재할 수 있다.

 

연락을 받을 수 있는 사람들 중 가장 마지막으로 연락을 받고, 그 중 가장 큰 번호를 구한다.

 

from collections import deque

def BFS(i):

    depth[i] = 1 # 깊이 저장
    q = deque([i]) # 큐에 초기값 세팅

    while q:

        now = q.popleft() # 큐에서 값을 꺼낸다.

        for p in graph[now]: # 연결리스트가 있고
            if not depth[p]: # 연락하지 않았으면
                depth[p] = depth[now]+1 # 이전 노드의 깊이 +1
                q.append(p) # 큐에 삽입
            

T = 10 # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N, S = map(int, input().split()) # 입력받는 데이터의 길이, 시작점
    A = list(map(int, input().split())) # 데이터 총
    graph = [[] for i in range(101)] # 인접 리스트

    for i in range(0, N, 2):
        s, e = A[i], A[i+1] # 시작점, 도착점
        graph[s].append(e) #그래프에 저장

    depth = [0 for i in range(101)] # 깊이 depth를 저장하는 배열
    BFS(S) # 탐색 시작

    max_depth = max(depth) # 가장 늦게 연락받은 순서
    dep = [i for i in range(101) if depth[i]==max_depth] # 가장 늦게 연락받은 사람들 구하기
    answer = max(dep) # 가장 큰 번호를 가진 사람 구하기


    print("#%d %d" %(test_case, answer))

 

 

 

[문제풀이]

---

 

BFS로 시작 번호에서 시작해서 각 노드까지 닿는 깊이를 구하면 되는 문제다.

 

이렇게, 시작점과 그래프가 주어진다.

depth = [0 for i in range(101)] # 깊이 depth를 저장하는 배열
BFS(S) # 탐색 시작

 

그럼 깊이를 저장하는 배열 depth를 선언한 후, 깊이 우선 탐색 BFS로 탐색한다.

큐에 넣고 각 노드를 순회하면서 갈 수 있는 모든 노드를 탐색해 깊이를 구한다.

 

 

그럼 이렇게 연락받을 수 있는 사람은 각각 n번째로 탐색했는지 알 수 있게 된다.

그럼 이 depth가 가장 높은 순서가 답인데, 이때 여러 명일 수 있다.

max_depth = max(depth) # 가장 늦게 연락받은 순서

 

그래서 이렇게 가장 늦게 연락받은 순서, 즉 최대 깊이를 우선 구한다.

dep = [i for i in range(101) if depth[i]==max_depth] # 가장 늦게 연락받은 사람들 구하기
answer = max(dep) # 가장 큰 번호를 가진 사람 구하기

 

그 후 최대 깊이와 동일한 깊이를 갖는 사람들, 즉 가장 늦게 연락받은 사람들을 구한다.

그리고 구한 사람들 중 가장 큰 번호를 가진 사람을 구하면 문제 해결된다.