문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
- 입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.풀이방법
주저리 주저리
처음 이 문제를 보고 푼 소스코드는 다음과 같다. 엄청 쉽다고 생각하고, 단순 구현해서 풀었는데 메모리 초과가 나더라.. 😥
- 단순 구현
import sys input = sys.stdin input = open("input.txt","rt")
n, m = map(int,input.readline().split())
board = [[0] * (n+1) for _ in range(n+1)]
computers = [0] * (n+1)
for _ in range(m):
a, b = map(int,input.readline().split())
board[b][a] = 1 #a는 b를 신뢰한다 -> b의 신뢰자는 a임을 1로 나타낸다.
computers[b] += 1 #b에 연결된 신뢰 컴퓨터의 수
for i in range(n+1):
if board[i][b] == 1: #b가 신뢰하는 컴퓨터인가?
computers[i] += computers[b]
top = max(computers)
for i in range(len(computers)):
if top <= computers[i]:
print(i, end=' ')
그래서 다른 소스코드들을 참고해보았더니, 탐색으로 풀어야 메모리 초과를 통과할 수 있었다. 하지만 탐색으로 변경해도 `python3`에서의 시간초과는 불가피했다. 그래서 `pypy3`으로 시도했다.
### 풀이 과정
주어진 입력을 보면, 2 3은 `2 신뢰 3`이고, 이는 **3번 컴퓨터가 해킹당하면 2번 컴퓨터도 해킹할 수 있다.** 를 나타낸다. 따라서 이후에는 3을 교주, 2를 추종자라고 칭하겠다. *(3을 신뢰하니..)*
배열에 교주의 인덱스에 추종자들을 모두 삽입한다. 예를 들어 3을 추종하는 추종자가 1,3,5인 경우에는 `배열[3] = [1,3,5]`와 같이 되도록.
그리고 이후 `bfs`를 이용한다.
* 각 인덱스별로 bfs를 돌려 해당 인덱스의 추종자를 q에 삽입
* 추종자의 추종자를 q에 삽입
* q가 없을 때까지 진행
* **q에 삽입될 때마다 추종자의 횟수를 카운팅**
이 과정을 통해 교주별 추종자 수를 구하고, max값을 갖는 교주의 인덱스를 출력함으로서 해결할 수 있다.
## 소스코드
`Pypy3`import sys, collections
input = sys.stdin
def bfs(idx):
q = collections.deque()
q.append(idx)
visit = [0] * (n+1)
visit[idx] = 1
cnt = 1
while q:
i = q.popleft()
for j in board[i]:
if not visit[j]: #아직 방문하지 않았다면
q.append(j)
visit[j] = 1
cnt += 1
return cnt
n, m = map(int,input.readline().split())
board = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input.readline().split())
board[b].append(a)
cnt = [-1] * (n+1)
for i in range(1, n+1):
cnt[i] = bfs(i)
top = max(cnt)
for i in range(len(cnt)):
if cnt[i] == top:
print(i, end = ' ')
```