효율적인 해킹(백준 1325번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가? ✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

python으로 풀 수 없는 문제였음

문제

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

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

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

나의 풀이(정답 참고)

import sys
from collections import deque

def BFS(graph,i,N):
    queue=deque()
    visited=[False]*(N+1)
    visited[i]=True
    queue.append(i)
    count=1
    while queue:
        v=queue.popleft()
        for g in graph[v]:
            if not visited[g]:
                queue.append(g)
                visited[g]=True
                count+=1
    return count

N,M=map(int,input().split())

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

for _ in range(M):
    n1,n2=map(int,sys.stdin.readline().strip().split())
    graph[n2].append(n1)
answer=[]
max_count=-1
for g in range(1,N+1):
    c=BFS(graph,g,N)
    if c>max_count:
        answer=[g]
        max_count=c
    elif c==max_count:
        answer.append(g)

print(*answer)

• BFS를 사용해서 문제를 풀었고, 정답 풀이를 참고하였다. (시간 초과로 인해 Python으로 풀 수 없는 문제라서 pypy로 제출하였다)
• Graph는 평소 BFS와 DFS문제를 풀 때처럼, node끼리 서로 연결되어 있는 것이 아니다. 일방적인 방향으로만 이어져 있기 때문에 다른 방식으로 graph에 표기하였다. (2-3의 의미는 2→3과 같음)