Contact Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1238

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

비상연락망과 연락을 시작하는 당번에 대한 정보가 주어질 때, 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 함수를 작성하시오.

 

 

입력

입력의 첫 번째 줄에는 입력 받는 데이터의 길이와 시작점이 주어진다. 그 다음 줄에 입력받는 데이터는 {from, to, from, to, …} 의 순서로 해석되며 예시의 경우는 {2, 7, 11, 6, 6, 2, 2, 15, 15, 4, 4, 2, 4, 10, 7, 1, 1, 7, 1, 8, 1, 17, 3, 22}와 같다. 그런데 순서에는 상관이 없으므로 다음과 같이 주어진 인풋도 동일한 비상연락망을 나타낸다 (같은 비상연락망을 표현하는 다양한 인풋이 존재 가능하다). {1, 17, 3, 22, 1, 8, 1, 7, 7, 1, 2, 7, 2, 15, 15, 4, 6, 2, 11, 6, 4, 10, 4, 2} 다음과 같이 동일한 {from, to}쌍이 여러 번 반복되는 경우도 있으며, 한 번 기록된 경우와 여러 번 기록된 경우의 차이는 없다. {1, 17, 1, 17, 1, 17, 3, 22, 1, 8, 1, 7, 7, 1, 2, 7, 2, 15, 15, 4, 6, 2, 11, 6, 4, 10, 11, 6, 4, 2}

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

예시

입력

출력

24 2 1 17 3 22 1 8 1 7 7 1 2 7 2 15 15 4 6 2 11 6 4 10 4 2 300 42 42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 48 27 72 39 70 13 68 100 36 95 4 12 23 34 74 65 42 12 54 69 48 45 63 58 38 60 24 42 30 79 17 36 91 43 89 7 41 43 65 49 47 6 91 30 71 51 7 2 94 49 30 24 85 55 57 41 67 77 32 9 45 40 27 24 38 39 19 83 30 42 34 16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 51 51 42 25 67 31 8 92 8 38 58 88 54 84 46 10 10 59 22 89 23 47 7 31 14 69 1 92 63 56 11 60 25 38 49 84 96 42 3 51 92 37 75 21 97 22 49 100 69 85 82 35 54 100 19 39 1 89 28 68 29 94 49 84 8 22 11 18 14 15 10 17 36 52 1 50 20 57 99 4 25 9 45 10 90 3 96 86 94 44 24 88 15 4 49 1 59 19 81 97 99 82 90 99 10 58 73 23 39 93 39 80 91 58 59 92 16 89 57 12 3 35 73 56 29 47 63 87 76 34 70 43 45 17 82 99 23 52 22 100 58 77 93 90 76 13 1 11 4 70 62 89 2 90 56 24 3 86 83 86 89 27 18 58 33 33 70 55 22 90  …

#1 17 #2 96 …

 

---

2. 문제풀이

전형적인 BFS문제이다. 한쪽으로 깊이 들어가는 방식(DFS)가 아니라 넓게 퍼질때 마지막에 퍼지는 지점에서 제일 큰번호를 출력하는 문제다. queue를 이용하여 bfs를 구현한다. 큐를 하나만 사용할수도 있지만 이런 문제의 경우 2개의 큐를 이용하면 좀더 편하게 할 수 있다. 임시큐를 만들어 놓고 현재큐가 빌때까지 반복을하는데 전파가 가능하다면 임시큐에 데이터를 추가한다. 큐가 비었다면 임시큐를 현재큐에 넣어주고 비워준다. 큐가비었는데 임시큐가 비었다면 그것은 전파의 마지막단계라고 판단한다. 큐가 반복될때마다 큰 값을 저장하고 있다가 전파가 끝나면 그 값을 리턴하면 된다.

---

3. 소스코드

 

#D4 1238 Contact
 
#BFS를 이용한 풀이
def bfs(queue):
    global result
    #큐가 빌때까지 반복
    while queue:
        second_queue = []
        temp_result = 0
        while queue:
            #꺼내서 사용하고 사용체크
            temp = queue.pop()
            use_check[temp] = True
            #현재 전파상태에서 최댓값 찾기
            if temp > temp_result:
                temp_result = temp
            #연결되어있는부분 큐에 넣기
            while connect_list[temp]:
                s_temp = connect_list[temp].pop()
                #이미 들른곳이라면 패스
                if use_check[s_temp]: continue
                second_queue.append(s_temp)
        #가야할 장소가 있다면 bfs다시 돌리기
        if second_queue:
            queue = second_queue
    #큐가 비어있다면 마지막 전파단계이다.
    result = temp_result
 
 
for t in range(10):
    connect_list = [set() for _ in range(101)]
    use_check = [False] * 101
    length, start = map(int, input().split())
    temp_list = list(map(int, input().split()))
    for i in range(0, length, 2):
        connect_list[temp_list[i]].add(temp_list[i+1])
    result = 0
    bfs([start])
    print('#{} {}'.format(t+1, result))