[알고리즘] 23일차 (효율적으로 해킹하기) #백준1325번

📌 문제 047) 효율적으로 해킹하기

시간 제한 5초, 실버 I, 백준 1325번

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

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

5 4 # 컴퓨터 개수(노드), 신뢰 관계 개수(에지)
3 1
3 2
4 3
5 3

출력

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

1 2

1단계 문제 분석

• N와 M의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않은 편이다. 이 문제에서 잘 확인해야 할 부분은 신뢰 관계가 A, B라고 했을 때, A가 B를 신뢰한다는 것이다.
• 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다.
• 그래프의 노드와 에지를 기준으로 이해하면 A라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B, C라고 하면 B, C는 A에게 신뢰받는 노드이다.

1. 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프를 표현한다.
2. 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 준다.
3. 탐색 종료 후, 신뢰도 리스트를 탐색해 신뢰도의 최댓값을 Max 값으로 지정하고, 신뢰도 리스트를 다시 탐색하면서 Max 값을 지니고 있는 노드를 오름차순 출력한다.

2단계 슈도 코드

N(노드 개수) M(에지 개수)
A(그래프 데이터 저장 인접 리스트)
answer(정답 리스트)

# BFS 구현하기
BFS:
	큐 자료구조에 시작 노드 삽입
    visited 리스트에 현재 노드 방문 기록
    while 큐가 비어 있을 때까지:
    	큐에서 노드 데이터를 가져오기
        if 현재 노드의 연결 노드 중 미 방문 노드:
        	visited 리스트 노드 방문 기록
            신규 노드 index의 정답 리스트값 증가
            큐에 노드 삽입

for M만큼 반복:
	A 인접 리스트에 그래프 데이터 저장

for i -> 1 ~ N:
	visited(방문 여부 저장) 초기화
	BFS(i) 실행 # 모든 노드로 BFS 실행

for i -> 1 ~ N:
	answer 리스트에서 가장 큰 수 찾기 -> maxVal

for i -> 1 ~ N:
	answer 리스트에서 maxVal와 같은 값을 가진 index를 정답으로 출력

3단계 코드 구현

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
A = [[] for _ in range(N+1)]
answer = [0] * (N+1)

def BFS(v): # BFS 탐색 함수 구현
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_Node = queue.popleft()
        for i in A[now_Node]:
            if not visited[i]:
                visited[i] = True
                answer[i] += 1 # 신규 노드 인덱스의 정답 리스트값을 증가
                queue.append(i)

for _ in range(M):
    S, E = map(int, input().split())
    A[S].append(E)

for i in range(1, N+1): # 모든 노드에서 BFS 실행
    visited = [False] * (N+1)
    BFS(i)

maxVal = 0
for i in range(1, N+1):
    maxVal = max(maxVal, answer[i])

for i in range(1, N+1):
    if maxVal == answer[i]:
        print(i, end=' ')