[백준] 1325번 파이썬 - 그래프(BFS), 시간 초과 해결

문제요약 (1325. 효율적인 해킹)

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

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

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

문제에 대한 해답이 맞는데 자꾸 시간 초과가 나는 경우, PyPy3로 언어를 바꾸고 제출해보도록 하는 것도 방법이다..
필자도 구글링하고 코드 수정만 엄청 많이 했었다.
( 자식 노드와 부모 노드 구분하기, 내장함수 max 대신 전역 변수 사용, C++로 변환 등.. )

 

1325번: 효율적인 해킹

 

풀이를 위한 부연 설명

• 그래프의 모든 노드를 타고 내려가야하므로 DFS, BFS 모두 사용 가능하다.
  • 취향에 맞춰 BFS로 구현했다.
• a가 b를 신뢰하는 경우, b를 해킹하면 a도 된다는 것이다. 
  • 즉 관계가 b -> a 느낌으로 생각해야한다.

• BFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드 

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
com = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    com[a].append(b)

comCnt = [0] *(n+1)

def check(n):
    que = deque()
    que.append(n)
    visited[n] = True
    while que:
        now = que.popleft()
        # 아래 자식 노드들로 가지를 뻗으므로 부모쪽을  + 1
        visited[now] = True
        comCnt[now] += 1
        for new in com[now]:
            if not visited[new]:
                que.append(new)

for i in range(n+1):
    check(i)
    visited = [False] * (n + 1)

tmpMax = max(comCnt)

for idx in range(n + 1):
    if comCnt[idx] == tmpMax:
        print(idx, end=" ")

 

 

 

기억할 점

• 노드들 간의 관계를 잘 생각해야한다.
• 파이썬이 잘 안될때는 PyPy3로 제출하자..