[이코테] 전보(2) - 코딩테스트 - 다른풀이

안녕하세요. 이번에는 이전에 풀었던 전보 - 다익스트라 알고리즘 풀이를 다른 방식으로 풀어보려고합니다.

다익스트라 풀이법은 아래의 링크로 들어가시면 보실 수 있습니다.

https://sonlife97.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8C-%EC%A0%84%EB%B3%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8%ED%92%80%EC%9D%B4

[이코테] 전보 - 코딩테스트 - 구체적인풀이

 

이번에는 BPS 너비 우선 탐색을 사용하여 메시지가 도달하는 데 걸리는 최대 시간과 도달한 도시의 수를 계산합니다. 

 

메시지를 퍼뜨리는 함수 정의

from collections import deque

# 메시지를 퍼뜨리는 함수 정의
def spread_message(graph, start):
    # 도시별로 메시지 도달 여부와 최소 시간을 저장하는 배열 초기화
    visited = [False] * (len(graph) + 1)
    time_to_reach = [0] * (len(graph) + 1)

    # 시작 도시를 큐에 추가하고 방문 표시
    queue = deque([(start, 0)])
    visited[start] = True

    # 메시지를 퍼뜨리는 과정
    while queue:
        current_city, time = queue.popleft()

        # 현재 도시와 연결된 다른 도시들을 확인
        for neighbor in graph[current_city]:
            if not visited[neighbor]:
                visited[neighbor] = True
                time_to_reach[neighbor] = time + 1
                queue.append((neighbor, time + 1))

    return visited, time_to_reach

 

이 함수는 전보를  퍼뜨리는 역할을 합니다. 시작 도시에서 출발하여 다른 도시들로 전보를 전파하며,  각 도시별로 전보 다달 여부와 최소 시간을 계산합니다.

 

start는 전보 전파를 시작할 도시의 인덱스를 나타냅니다.

visited는 각 도시의 전보 도달 여부를 나타내는 불리언 리스트입니다.

time_to_reach 는 각 도시까지 전보가 도달하는데 걸리는 최소 시간을 나태내는 리스트입니다. 초기에는 모든 도시의 시간이 0으로 초기화 합니다.

 

queue BFS를 위한 큐입니다. 초기에 시작 도시를 큐에 추가하고 방문 여부를 표시합니다.

 

큐에서 도시를 하나씩 꺼내면서 해당 도시와 연결된 다른 도시들을 확인하고,

아직 방문하지 않은 도시에 대해 전보 도달 여부와 최소 시간을 갱신하고 큐에 추가합니다.

 

입력받기

# 입력 받기
n, m, c = map(int, input().split())  # 도시 수, 통로 수, 시작 도시 C
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())  # x에서 y로 통로가 연결되어 있다.
    graph[x].append(y)

# 도시 C에서 메시지를 시작하고, 도시들에 메시지가 도달하는지 확인
visited, time_to_reach = spread_message(graph, c)

# 메시지가 도달한 도시 수와 가장 오래 걸리는 시간 구하기
count = sum(visited) - 1  # 시작 도시 C를 제외한 도시 수
max_time = max(time_to_reach[1:])  # 시작 도시 C를 제외한 도시 중에서 가장 오래 걸리는 시간

# 결과 출력
print(count, max_time)

 

 

전체 코드

from collections import deque

# 메시지를 퍼뜨리는 함수 정의
def spread_message(graph, start):
    # 도시별로 메시지 도달 여부와 최소 시간을 저장하는 배열 초기화
    visited = [False] * (len(graph) + 1)
    time_to_reach = [0] * (len(graph) + 1)

    # 시작 도시를 큐에 추가하고 방문 표시
    queue = deque([(start, 0)])
    visited[start] = True

    # 메시지를 퍼뜨리는 과정
    while queue:
        current_city, time = queue.popleft()

        # 현재 도시와 연결된 다른 도시들을 확인
        for neighbor in graph[current_city]:
            if not visited[neighbor]:
                visited[neighbor] = True
                time_to_reach[neighbor] = time + 1
                queue.append((neighbor, time + 1))

    return visited, time_to_reach

# 입력 받기
n, m, c = map(int, input().split())  # 도시 수, 통로 수, 시작 도시 C
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())  # x에서 y로 통로가 연결되어 있다.
    graph[x].append(y)

# 도시 C에서 메시지를 시작하고, 도시들에 메시지가 도달하는지 확인
visited, time_to_reach = spread_message(graph, c)

# 메시지가 도달한 도시 수와 가장 오래 걸리는 시간 구하기
count = sum(visited) - 1  # 시작 도시 C를 제외한 도시 수
max_time = max(time_to_reach[1:])  # 시작 도시 C를 제외한 도시 중에서 가장 오래 걸리는 시간

# 결과 출력
print(count, max_time)