[BOJ:1325] 효율적인 해킹

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

Note

프로그래머스의 전력망 나누기 문제를 풀다가 트리,그래프 자료구조관련 문제 연습이 필요하다고 느껴 풀이한 문제다.

python3에서 BFS, 재귀 DFS로 풀이하면 시간초과가 발생, pypy3에서 재귀 DFS 로 풀이하면 메모리초과 발생하지만 pypy3에서 파이썬의 list를 스택으로 이용하여 DFS로 트리 탐색 또는, BFS 탐색을 하면 해결된다.

A가 B를 신뢰하는 경우 B를 해킹하면 A도 해킹하는 컴퓨터 시스템이 있다. 입력은 첫 째줄에 전체 컴퓨터의 수 n, 연결 상태 m이 주어지고 다음 m번 줄에 걸쳐 A, B가 입력으로 주어진다. 입력 값을 통해 방향그래프를 만들고, 방향그래프를 탐색하면서 탐색가능한 노드의 수를 구하고, 가장 많은 탐색 노드를 갖는 노드를 오름차순으로 출력하면된다.

각 노드를 출발점으로 BFS. DFS를 통한 그래프를 탐색할 때 방문 노드 초기화를 해주지 않는 실수가 생겼다. 원인은 알고리즘을 설계하고 검증단계를 거치지 않고 바로 코드를 작성했기 때문에 생긴 문제라고 생각한다.

알고리즘

1. 입력값 A,B에 대하여 방향 그래프를 만든다.
2. 각 노드를 시작 점으로 하여 그래프 탐색을 하면서 탐색 가능한 노드의 수를 구한다.
3. 2에서 구한 노드의 수의 최대값을 갖는 노드를 오름차순으로 출력한다.

Code

pypy3 BFS

import sys
from collections import deque
def BFS(cur_node):
    global visited, tree
    visited[cur_node] = True
    q = deque()
    q.append(cur_node)
    cnt = 1

    while q:
        now = q.popleft()
        for next in tree[now]:
            if not visited[next]:
                q.append(next)
                visited[next] = True
                cnt += 1

    return cnt

input = sys.stdin.readline

n, m = map(int,input().split())

tree = [[] for _ in range(n+1)]
visited = [False]*(n+1)
child_cnt = [0]*(n+1)

for _ in range(m):
    a, b = map(int,input().split())
    tree[b].append(a)

max_cnt = -1

for start_node in range(1,n+1):
    visited = [False]*(n+1)
    child_cnt[start_node] = BFS(start_node)
    if max_cnt < child_cnt[start_node]:
        max_cnt = child_cnt[start_node]

for node_num, cnt in enumerate(child_cnt):
    if cnt == max_cnt:
        print(f"{node_num} ", end="")

Pypy3 list 활용, DFS

import sys
from collections import deque
def DFS(cur_node):
    global visited
    cnt = 1
    stack = [cur_node]
    visited[cur_node]= True

    while stack:
        now = stack.pop()
        for next in tree[now]:
            if not visited[next]:
                stack.append(next)
                visited[next] = True
                cnt += 1

    return cnt

input = sys.stdin.readline

n, m = map(int,input().split())

tree = [[] for _ in range(n+1)]
child_cnt = [0]*(n+1)

for _ in range(m):
    a, b = map(int,input().split())
    tree[b].append(a)

max_cnt = -1

for start_node in range(1,n+1):
    visited = [False]*(n+1)
    child_cnt[start_node] = DFS(start_node)
    if max_cnt < child_cnt[start_node]:
        max_cnt = child_cnt[start_node]

for node_num, cnt in enumerate(child_cnt):
    if cnt == max_cnt:
        print(f"{node_num} ", end="")