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

7867 단어 BFS/DFSBFS/DFS

문제

링크

코드

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

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

for _ in range(m) :
    a, b = map(int, input().split())
    # A가 B를 신뢰할 때, B를 해킹하면 A도 해킹할 수 있다
    # = B 하위에 A가 있음
    computer[b].append(a)

answer = [0] * (n+1)
for i in range(1, n+1) : 
	# 해당 컴퓨터 하위에 있는 컴퓨터가 없을 땐 넘어가기
    if len(computer[i]) == 0 :
        continue
    visited = [False] * (n+1)
    queue = deque([i])
    visited[i] = True
    cnt = 1
    # BFS 사용
    while queue : 
        q = queue.popleft()
        for c in computer[q] :
            if visited[c] == False:
                visited[c] = True
                queue.append(c)
                cnt += 1
    answer[i] = cnt

tmp = []
for j in range(1, n+1) :
    if max(answer) == answer[j] :
        tmp.append(str(j))

print(*tmp)
# 혹은 print(' '.join(tmp)

처음 코드를 계속 실행했을 때 계속 틀렸다고 나와서 다른 분들의 코드를 살펴봤다.
코드가 다른 건 거의 없었지만 그 중에서도 visited 부분이 달랐다.
나는 visited를 1씩 더해가면서 그 중 가장 큰 수를 answer 에 넣었지만,
다른 분들은 True, False로 판단하고 cnt라는 변수에 1씩 더해주었다.
visited를 바꿔서 풀어주니까 문제가 풀렸다!
뭐가 문제인지 모르겠지만..
그리고 python으로 돌리면 시간 초과가 계속 발생해서 pypy3으로 풀었다.

  • 새로 알게 된 정보
    배열에 있는 문자를 띄어쓰기를 포함해서 한 줄로 출력하고 싶으면

    *배열

을 하면 된다. ' '.join(배열) 과 같다.아무리 검색해도 나와있지 않고, 다른 분들의 코드에서 발견한 거라 그냥 주입식으로 외워야 겠다.

좋은 웹페이지 즐겨찾기