[백준] 1325 - 효율적인 해킹

1. 문제

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

2. 접근

1. 신뢰한다는 조건에서 트리 구조를 생각할 수 있었다 ( 최단경로도 비슷했다 ), a가 b를 신뢰하면 b 를 해킹하면 자동적으로 a도 해킹됨을 생각하고 graph에 데이터를 append 하자

2. 모든 노드들을 돌아보자. 당연히 노드가 1~N이니까 start 는 1이다.

3. 트리 구조로 그려 보고 해보면 현재 지점은 방문 처리하고, 그 graph에 있는 데이터로 거슬러 올라가면서 cnt를 증가시키고 해당 노드는 방문처리 해주자

4. 1~n개의 노드들을 전부 접근하면서 max_cnt 보다 값이 크면 res를 리셋해서 넣어주고 마지막에 배열 자체를 출력!

 

3. 풀이

# 1325 , 살버 1
from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # m은 간선 같은 역할

graph = [[] for _ in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    graph[b].append(a) # a가 b를 신뢰, b 해킹시 a 자동 해킹

def bfs(start):
    cnt = 1 # 지금 해킹한 node를 포함해야 하므로
    visited = [False] * (n+1)
    visited[start] = True
    q = deque([start])

    while q:
        current = q.popleft()

        for i in graph[current]:
            if not visited[i]:
                visited[i] = True
                cnt += 1
                q.append(i)
    return cnt

res = []
max_cnt = 1

for i in range(1,n+1):
    data = bfs(i)
    if data > max_cnt:
        max_cnt = data
        res = [i]
    if data == max_cnt:
        res.append(i)
print(*res)