백준 1325 - 효율적인 해킹

|

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

적절한 자료 구조가 떠오르지 않아서 우선 아래와 같은 방식으로

연결이 되면1, 연결이 없으면 0인 인접 행렬을 구현했다.

또한 문제를 잘 못 이해해서 모든 연결을 다 구해줬는데 결국 ‘‘가장 많은 컴퓨터를 해킹 하는 경우’’ 만 구하면 되므로 로직 자체의 수정과 자료 구조의 수정이 필요했다.

def dfs(x):
    #x: current state
    global cnt

    if sum(graph[x])==0:
        return

    for i, k in enumerate(graph[x]):
        if k == 1:
            cnt+=1
            dfs(i)

    return cnt

n, m = map(int, input().split())
answers = {}

graph = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[b-1][a-1] = 1

for i in range(n):
    cnt = 0
    answers[i+1] = dfs(i)

print(answers)

Comments