[백준] 1325번 효율적인 해킹 ★

💡문제접근

• 이 문제는 다른 문제와 다른 단방향 그래프 문제였다. 문제에서 A가 B를 신뢰하는 관계라고 가정할 때, B를 해킹하면 A를 해킹할 수 있다고 했기 때문에 B에 A를 추가하는 방식으로 코드를 작성해야한다는 것을 알고 코드를 작성했다.
• BFS 풀이는 가능했지만 DFS 풀이는 하지 못했다. 빈번한 시간초과와 메모리초과가 발생했고 결국 포기했다.

💡코드(메모리 : 215132KB, 시간 : 13132ms, PyPy3로 제출)

📌 Python BFS 코드(WA)

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

N, M = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().strip().split())
    graph[B].append(A)

visited = [False] * (N+1)

def BFS(start):
    queue = deque()
    queue.append(start)
    visited = [False] * (N+1)
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
    return visited.count(True)

hacking = [0] * (N+1)
for i in range(1, N+1):
    hacking[i] = BFS(i)

Max = max(hacking)
for i in range(N+1):
    if hacking[i] == Max:
        print(i, end = " ")

📌 Python DFS 코드(TLE)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M = map(int, input().strip().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().strip().split())
    graph[B].append(A)


def DFS(start, visited):
    global depth
    visited[start][0] = True
    for i in graph[start]:
        if not visited[i][0]:
            depth += 1
            DFS(i, visited)
    return depth


visited = [[False, 0] for _ in range(N + 1)]
hacking = [0] * (N + 1)
for i in range(1, N + 1):
    depth = 1
    visited = [[False, 0] for _ in range(N + 1)]
    hacking[i] = DFS(i, visited)

Max = max(hacking)
for i in range(1, N+1):
    if hacking[i] == Max:
        print(i, end = " ")

💡소요시간 : BFS(31m) + DFS(26m)