[Python] SW Expert Academy #1238 Contact

📚문제: #1238 Contact(D4)

전체 코드

# 1238. Contact

from collections import deque

# BFS 함수
def BFS(v, s, gph, n):
    
    # 시작
    pair = [s, 0]
    
    # 큐 선언
    q = deque()
    q.append(pair)
    
    # 시작지점 방문처리
    v[s] = True
    
    # 모든 방문노드들을 저장하는 리스트
    array = []
    
    # 큐가 빌 때까지 반복
    while q:
        
        # 꺼낸 노드, 거리
        cur, dist = q.popleft()
        
        # 추가
        array.append((cur, dist))
        
        # 꺼낸 노드의 이웃에 대해서 조사
        for neighbor in gph[cur]:
            
            # 아직 방문 안했을 때
            if not v[neighbor]:
                
                # 방문 처리
                v[neighbor] = True
                
                # 큐에 추가
                q.append([neighbor, dist + 1])
    
    # 거리가 제일 먼 순서로 정렬 후, 노드 번호가 가장 큰 순서로 정렬
    array.sort(key = lambda x:(-x[1], -x[0]))
    
    # 답
    ans = array[0][0]
     
    # 답안 출력
    print("#{} {}".format(n, ans))
    
# 10개의 테스트 케이스
for t in range(1, 10+1):
    
    # 길이와 시작점이 주어진다.
    l, s = map(int, input().split())
    
    # from, to 순서로 데이터가 주어진다.
    seq = list(map(int, input().split()))
    
    # 그래프 초기화 (1번 ~ 100번)
    graph = [[] for _ in range(100+1)]
    
    # 방문여부 리스트
    visited = [False] * (100+1)
    
    # 그래프에 관계를 추가한다.
    for i in range(0, l, 2):
        
        graph[seq[i]].append(seq[i+1])
    
    # 그래프에서 중복을 제거한다.
    for i in range(1, 100+1):
        
        graph[i] = list(set(graph[i]))
        
    # 함수 실행
    BFS(visited, s, graph, t)

아이디어

노드 간의 관계를 그래프로 표현, 시작지점에서부터 이웃노드를 탐색할 때 BFS를 활용한다. 도달할 수 있는 이웃노드가 있을 때 현재까지 거리에서 1씩 추가해준다. 마지막에 거리가 가장 먼 노드 중에서 가장 숫자가 큰 값을 출력한다.