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

취준한지가 얼마나 지났다고 기본적인 알고리즘도 못풀겠더군요ㅜㅜ

그 중 하나가 DFS, BFS...

알고리즘은 정말 꾸준히 풀어야 하는것 같아요.

 

이번 문제는 DFS와 관련된 문제입니다.

문제 출처: https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

문제

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

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

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

입력

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

출력

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

---

저는 이 문제를 보고 'DP를 이용해야겠다.'라는 생각이 들더군요.

결론부터 말하면 제가 생각하는 방식으로 DP를 활용하지 못하겠더라구요.

cycle이 있는 경우가 문제가 되었어요.

 

* 생각했던 방식

- 1~N 순서대로 컴퓨터가 해킹의 출발점이 되었을 때, 총 몇개의 컴퓨터를 해킹할 수 있는지 memorization

- 각 컴퓨터마다 총 몇개의 컴퓨터를 해킹할 수 있는지는 DFS 이용

- 만약 DFS를 하는 중에 memorization된 컴퓨터가 있다면 해당 컴퓨터는 stack에 넣지 않고 memorization된 값을 이용

 

* 반례

(입력)

3 3

1 2

2 3

3 1

+ 또한 처음에는 '만약 A가 B를 신뢰하는 경우에는 출력해야하는 컴퓨터 list에는 A가 포함되지 않겠구나'라고 생각했는데, 이런 cycle 때문에 성립하지 않더라고요.

 

따라서 그냥 가장 단순하게 생각할 수 있는 모든 점에서부터 DFS를 사용하여 방문할 수 있는 컴퓨터의 개수를 출력하기로 했습니다. 그리고 PASS했습니다.

단순히 모든 점에서부터 DFS를 한 것이기 때문에 풀이법에 특별히 소개해 드릴 점은 없습니다.

 

[풀이1. DFS이용]

N, M = map(int, input().split())
info = [[] for _ in range(N)]
max_cnt = -1
answer = []

for _ in range(M):
    com2, com1 = map(lambda x: int(x)-1, input().split())
    info[com1].append(com2)

for com1 in range(N):
    is_visited = [False] * N
    if len(info[com1]) > 0:
        cnt = 1
        is_visited[com1] = True
        stack = [com1]

        while len(stack) > 0:
            cur = stack.pop()

            for new_com2 in info[cur]:
                if is_visited[new_com2] is False:
                    cnt += 1
                    stack.append(new_com2)
                    is_visited[new_com2] = True

        if max_cnt < cnt:
            max_cnt = cnt
            answer = [com1]
        elif max_cnt == cnt:
            answer.append(com1)

answer.sort()
answer = list(map(lambda x: x+1, answer))

for ele in answer:
    print(ele, end=" ")

 

[풀이2. BFS이용]

import collections

N, M = map(int, input().split())
info = [[] for _ in range(N+1)]

max_cnt = -1
answer = []

for _ in range(M):
    com2, com1 = map(int, input().split())
    info[com1].append(com2)

for com1 in range(1, N+1):
    visit = [False] * (N+1)
    q = collections.deque()
    cnt = 0

    visit[com1] = True
    q.append(com1)
    cnt += 1

    while len(q) > 0:
        cur = q.popleft()

        for new_com2 in info[cur]:
            if visit[new_com2] is False:
                visit[new_com2] = True
                q.append(new_com2)
                cnt += 1

    if max_cnt < cnt:
        max_cnt = cnt
        answer = [com1]
    elif max_cnt == cnt:
        answer.append(com1)

answer.sort()
for ele in answer:
    print(ele, end=" ")