[Python] 백준 / silver / 1325 : 효율적인 해킹

문제 링크 : https://www.acmicpc.net/problem/1325

BFS 문제다. BFS 수행 과정을 다시 되새겨볼 수 있는 문제였던 것 같다. 이 문제에서 그래프는 사이클을 가질 수 있고, directed graph 다. 처음에 생각없이 BFS 큐에 node 번호와 num 을 넣어 다음 노드를 탐색 할때마다 num 이 증가하도록 구현했는데, 그렇게 하면 반례가 생겼다.

큐를 탐색하면서 큐에 변수를 담아가며 조작할지, 전역변수로 생각하고 조작할지 잘 파악해야 되겠다고 생각이 들었다.

오답 파이썬 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[B].append(A)

howManyHack = [0] * (N+1)

for i in range(1, N+1):
    visit = [False] * (N + 1)
    howMany = 1
    # BFS
    q = deque()
    q.append((i, 1))
    visit[i] = True
    while q:
        now, num = q.popleft()
        for x in graph[now]:
            if not visit[x]:
                q.append((x, num+1))
                howMany = max(howMany, num+1)
                visit[x] = True
    howManyHack[i] = howMany

print(howManyHack)
answer = ""
for i in range(1, N+1):
    if howManyHack[i] == max(howManyHack):
        answer += str(i)+" "

print(answer[:-1])

반례

1번 노드도 howManyHack 값이 2, 2번 노드도 howManyHack 값이 2가 되기 때문에 오답처리된다.

정답 파이썬 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[B].append(A)

howManyHack = [0] * (N+1)

for i in range(1, N+1):
    visit = [False] * (N + 1)
    howMany = 1
    # BFS
    q = deque()
    q.append(i)
    visit[i] = True
    while q:
        now = q.popleft()
        for x in graph[now]:
            if not visit[x]:
                q.append(x)
                howMany += 1
                visit[x] = True
    howManyHack[i] = howMany

#print(howManyHack)
answer = ""
for i in range(1, N+1):
    if howManyHack[i] == max(howManyHack):
        answer += str(i)+" "

print(answer[:-1])