백준 1325-효율적인 해킹 (파이썬)

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

문제

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

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

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

입력

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

출력

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

 

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

---

시나리오

N개의 정점(컴퓨터)과 M개의 간선(컴퓨터 간 신뢰관계)이 주어진다.

이 때, 신뢰하는 관계에서 A가 B를 신뢰하는 경우 B를 해킹하면 A도 해킹할 수 있다고 했다.

따라서 컴퓨터 간의 관계를 B에서 A로 가는 방향 그래프로 설정하고 간선의 크기가 \(정점의 크기^2\) 보다 작으므로 인접리스트를 생성해 문제를 해결한다.

예시를 방향 그래프로 그려보면 위와 같다.

 

풀이 1(DFS)

처음 접근할 때는 어차피 그래프의 모든 정점을 방문해야 하고 딱히 최단거리를 구하는 문제가 아니기 때문에 DFS로 풀어야겠다는 생각을 했다.

그렇게 구현을 마쳤고 아래 코드로 제출을 했다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

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

hack = [0] * (n + 1)


def dfs(now, cnt):
    for nxt in adj[now]:
        cnt = dfs(nxt, cnt + 1)
    return cnt


for i in range(1, n + 1):
    hack[i] = dfs(i, 1)

for i in range(1, n + 1):
    if hack[i] == max(hack):
        print(i, end=' ')

제출한 결과, 시간초과가 발생했다. 어떻게 하면 시간을 줄일 수 있을까 고민하다가 풀이 2의 코드를 작성했다.

풀이 2 (DFS, 풀이 1 개선)

이전 코드와 차이점은

1. 방문 정점을 저장하는 리스트chk를 만들었고 이미 방문한 정점을 재방문하지 않도록 했다.
2. 또한 '부모 노드의 해킹 가능한 컴퓨터 대수 = 자기 자신 + 자식 노드의 해킹 가능한 컴퓨터 대수'이기 때문에 'chk[노드 번호]= 해킹 가능한 대수'로 값을 설정했으며, 특정 노드의 자식 노드가 이미 방문한 노드일 경우 탐색을 중단하고 자식 노드의 해킹 대수 + 1을 부모 노드의 해킹 대수로 설정하여 chk[부모노드]의 값으로 넣어주었다.

import sys

sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

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

chk = [0] * (n + 1)


def dfs(now):
	#현재 노드의 자식 노드가 없을 경우 해킹 대수=1, return해준다.
    if not adj[now]:
        chk[now] = 1
        return
    for nxt in adj[now]:
    	#자식 노드가 이미 방문한 노드가 아닐 경우
        if not chk[nxt]:
            dfs(nxt)
            현재 노드의 해킹 대수 = 0 + 자식 노드의 대수
            chk[now] += chk[nxt]
    	#자식 노드가 이미 방문한 노드일 경우
        else:
            현재 노드의 해킹 대수 = 0 + 자식 노드의 대수
            chk[now] += chk[nxt]
    #함수 종료 전 현재 노드의 해킹 대수에 자기 자신을 포함해서 개수를 맞춰준다.
    chk[now] += 1


for i in range(n + 1):
	#방문하지 않은 노드만 dfs하도록 하여, 루트 노드일 때만 dfs를 호출할 수 있도록 했다.
    if not chk[i]:
        dfs(i)

#그래프 완전탐색 후 해킹 가능한 대수가 가장 많은 노드를 선별하기 위한 코드
for i in range(1, n + 1):
    if chk[i] == max(chk):
        print(i, end=' ')

풀이 1의 시간복잡도 문제를 크게 개선했다고 생각하고 제출했다. 

이번엔 메모리초과가 나왔다.. 

 

구글링 해보니 애초에 제한이 타이트한 문제라 최대한 효율적으로 구현해서 pypy로 돌려야 정답을 맞힐 수 있는 문제였다.

그리고 백준 질문을 보니 파이썬으로 dfs와 bfs 동시에 구현해서 풀었을 때 bfs는 정답이 나오지만 dfs는 오답이 나오는 경우도 있었다.

 

그렇게 해서 마지막 풀이는 BFS로 구현했다..

풀이 3(BFS)

제출해서 정답을 맞았다는 코드를 참고해서 작성했다. 풀이 1처럼 n번 반복하여 bfs함수를 호출한 뒤 그 결과를 리스트에 기록하는 방법을 사용했다.

다만 기본적으로 DFS보다 BFS속도가 더 빠르기 때문에 시도해볼만한 가치가 있었다.

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
result = [0] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    adj[b].append(a)


def bfs(i):
	#방문여부를 호출 할 때마다 초기화한다.
    chk = [0] * (n + 1)
    chk[i] = 1
    dq = deque()
    dq.append(i)
    cnt = 1
    while dq:
        s = dq.popleft()
        for nxt in adj[s]:
            if not chk[nxt]:
                dq.append(nxt)
                chk[s] = 1
                cnt += 1
    return cnt


#BFS N번 호출
for i in range(n + 1):
    result[i] = bfs(i)

for i in range(1, n + 1):
    if result[i] == max(result):
        print(i, end=' ')

하지만 제출한 결과 이 또한 시간초과가 발생했다. 

혹시나 싶어 통과했다는 코드를 여러 개 제출해도 그중 절반 정도만 통과하더라는.. 

이쯤 되면 평가방식이 잘못됐다고 생각하고 한 가지 문제를 여러 방식으로 풀었다는 사실에 만족해야겠다..

 

시간복잡도

그래프 구조를 저장하고 사용할 때 인접리스트, 인접행렬 이 중 어떤 것을 사용하는지에 따라 시간복잡도가 달라진다.

인접행렬: \(O(V^2)\)

인접리스트: \(O(V+E)\)

이 문제는 정점의 개수는 최대 10,000 간선의 개수는 최대 100,000이므로

인접리스트 사용 시: \(O(N+M) * O(N+1) = O(N^2 + NM) \)즉, \(10^8 + 10^9\)

인접행렬 사용 시: \(O(N^2) * O(N) = O(N^3)\)즉, \(10^12\  \)이다.

따라서 인접리스트를 사용하는 게 유리하다. 하지만 제한시간이 5초이기 때문에 최대 연산을 따져보면 대략 5억 번 정도인데 둘 중 어느 것을 사용하더라도 이를 훨씬 초과하지만 단방향 그래프인 만큼 위 연산 횟수만큼은 가지 않을 것이다.

 

 

추후 과제

다른 사람들의 그래프 탐색 문제 풀이를 검색해보면 DFS중에서도 스택을 이용한 DFS풀이법도 종종 있었다.

알고리즘별 실행 속도를 비교해보면 BFS < 스택을 이용한 DFS < 재귀를 이용한 DFS 순이라고 한다.

특히 이 문제에서 스택을 이용한 DFS풀이를 제출했을 때 BFS보다는 느리지만 정답처리가 된만큼 재귀를 이용한 DFS보다는 성능이 좋았다.

여태까지 DFS를 구현할 때 재귀를 이용한 DFS만 구현했었는데 스택을 이용한 DFS도 풀이법도 익혀두자.