백준 온라인 저지: 문제 풀러 가기

1. 문제 요약

알고리즘 분류 | 완전 탐색

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력 첫째 줄에, N과 M이 들어온다. (N <= 10,000, M <= 100,000)

둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다.

컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력 첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

1줄 요약) 그래프 탐색하자!

2. 접근 방식

1. 신뢰하는 관계 => 일방향 간선으로 생각해서 그래프 탐색

   • 너비우선(BFS)으로 탐색하면서 방문한 정점의 수를 기록한다.

2. 최대치를 찾아야 하므로 모든 경우를 탐색한다.

   • 최다 정점을 방문한 시작 정점의 번호를 정답으로 출력한다.

풀이 >

import sys
input = sys.stdin.readline # 중요!!!!, 입력 속도가 느리면 통과 불가능.
from collections import deque

# 너비 우선 탐색
def bfs(s):
    D = 0
    q = deque()
    q.append(s)
    visit = [0] * (N + 1)
    visit[s] = 1
    while q:
        here = q.popleft()
        D += 1
        for w in G[here]:
            if not visit[w]:
                visit[w] = 1
                q.append(w)
    return D # 방문한 정점의 수 D를 리턴한다.
                
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    G[b].append(a)
mxd = 0
result = []
for i in range(1, N + 1):
    if G[i]:
        tmp = bfs(i) # 리턴값을 받아서 최대값과 비교
        if mxd <= tmp:
            if mxd < tmp:
                result = []
            mxd = tmp
            result.append(i)
print(*result)

3. 감상

• 시간제한이 빡빡한 문제
• import sys;input = sys.stdin.readline 시간 초과시 1순위로 시도해 볼 옵션이다.
• 트리/ 그래프 순회문제는 고정된 코드를 쓰는 경우가 많으므로 익숙한 형태로 숙지해놓으면 좋다.