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

문제

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

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

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

 

★ 시작하기 전에

dfs문제. 한방향 연관 노드 리스트를 만들고 모든 경우의 수를 다 돌아본 후, 최솟값을 구하면 될 것이다! 라고 생각했다.

물론 처음부터 생각한건 아니지만, dfs 형식만 안다면 어렵지 않을 것이라 생각했다.

도전!

 

import sys

input = sys.stdin.readline

# dfs 함수로 재귀하여 구해보았다.
def dfs(i, word):
    global maxi
    word.append(i)
    if board[i] == []:
        if len(word)-1 >= maxi:
            maxi = len(word)-1
            ans.append(word[0])
            return
    else:
        for w in board[i]:
            if visited[w] == 0:
                visited[w] = 1
                dfs(w, word)
                #visited = 0한 이유는 다음 노드로 내려갈때 다른곳을 지나 가는 경우 고려
                visited[w] = 0   
                word.pop()


n, m = map(int,input().split())
board = [ [] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    board[b].append(a)

ans = []
maxi = 0
# isstart = [0 for _ in range(n+1)]
for start in range(1,n+1):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    word = []
    dfs(start, word)
    
print(*set(ans))

마지막으로 고른 풀이.... 이전에 2개가 더 있다.. 하지만... 모두모두모두 시간 초과 ㅠㅠ

결국 구글의 도움을 받아봤는데... 그들도 시간 초과..

무슨일이지??????

간단한 줄 알았던 문제가 시간 초과나니까 어떻게 손을 대야할지 모르겠다..

 

스터디에도 물어보고 이런저런 고민만 한 끝에.. 내 답을 정답으로 인정!해보자 ㅎㅎ

dfs에 대한 문제는 계속 풀고 또 풀어보자.