이번 문제는 dfs나 bfs를 이용해 역방향 그래프를 만드는 문제였다.
하... 테스트 케이스로 돌리면 결과 잘 나오는데, 시간초과 아니면 출력초과가 계속 떠서 애먹은 문제였다.
보이심...? 어느 부분때문에 에러나는건지 알 수가 없어서 나 정말 미치기 직전까지 갔어요.
문제
https://www.acmicpc.net/problem/1325
접근
A -> B 이면, B를 해킹했을 때 A도 같이 해킹된다.
그럼 B로 접근하면 효율적으로 해킹할 수 있는데 B도 어느 노드한테는 A인 포지션일테니,
1. 노드들 중에서 B 포지션으로 제일 많이 언급되는 노드를 저장하고
2. 저장한 노드들이 신뢰하는 노드들(B 포지션) 타고타고 가서 더이상 B포지션의 노드가 없을 때까지 그래프 생성
이 로직으로 짜면 제일 신뢰받는 노드들부터 시작하니까 모든 그래프를 그리지 않아도 돼서 시간 단축될 거라 생각했다.
(개큰 오산이었음을...)
개인적으로 재귀 함수는 선호하지 않아서 while문으로 bfs 방식을 썼다.
😎bfs (너비 우선 탐색)
- dfs와 달리 '깊게' 탐색하지 않고 '넓게' 탐색하는 방식이다.
- 루트 또는 임의의 노드부터 시작해서 인접한 노드를 먼저 탐색하는 방식으로, 두 노드 사이의 최단경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색
일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
bfs 방식으로 짠 코드는 아래와 같다.
import copy
# 가장 신뢰받는 노드의 부모 찾고, 그 부모가 신뢰하는 노드까지 다 찾음
n,m = map(int, input().split())
trusted = [0] * (n+1)
edges = []
for _ in range(m):
u, w = map(int, input().split())
edges.append((u, w))
# 각 노드들이 몇 번 신뢰받는지 카운트
trusted[w] += 1
cnt = 0
visited = [0] * (n+1)
result= []
# 가장 큰 값이 있는 모든 인덱스 찾기
max_val = max(trusted)
memory = [i for i, val in enumerate(trusted) if val == max_val]
#print('memory : ', memory)
result = []
queue = copy.copy(memory)
while memory:
memory_1 = memory[0]
visited[memory[0]] = 1
memory.pop(0)
for u, w in edges:
if u == memory_1 and w in queue:
queue.remove(w)
result.append(w)
if u == memory_1 and visited[w] == 0:
result.append(w)
memory.append(w)
visited[w] = 1
#print(memory)
result.sort()
for i in result:
print(i, end=" ")
* trusted : 입력 받을 때 각 노드들이 B 포지션으로 몇 번 등장하는지 저장하는 배열
배열의 인덱스 -> 노드 숫자, 요소 -> 등장 횟수로 저장
* memory : trusted 배열에서 가장 많이 B 포지션으로 등장한 노드를 추출해 저장한 배열
* while 문 : bfs 실행문
가로쌍을 하나의 set로 저장한 edges 배열 순회하며 탐색 순서 노드가 A 포지션이며, 얘가 신뢰하는 w 노드가 한 번도 방문하지 않은 노드이면 result 배열과 memory 배열에 넣는다.
여기서 memory 배열은 탐색 대상 배열이 되어, 한 번 돌 때마다 0 번 인덱스에 있는 노드가 탐색된다.
이 코드의 문제점은,, 앞서 말한 것처럼 시간 초과가 난다는 것이었다.
for문 한 번 돌릴 때마다 edges 배열을 모두 순회해야 해서 간단한 그래프인 경우 문제가 없지만천개, 만개의 노드가 있는 그래프를 만들려면 엄청난 부담이 든다.
그리고 발상이 좀 허술한게 신뢰가 두터운 노드로 시작한다고 해도while문에서 언급되지 않은 노드가 또 연결되어 있을 수도 있는데 얘네를 방문하지 않고 지나가면 미완성 그래프인 셈이다.애초에 로직 자체가 허술해서 모든 테스트 케이스를 통과하지 못했을 것이다.
코드
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
# 역방향 그래프 만들기
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph[b].append(a)
print(graph)
def bfs(start):
visited = [0] * (n + 1)
queue = deque([start])
visited[start] = 1
count = 1
while queue:
current = queue.popleft()
for next_node in graph[current]:
if not visited[next_node]:
visited[next_node] = 1
queue.append(next_node)
count += 1
return count
result = []
max_count = -1
for i in range(1, n + 1):
hacked = bfs(i)
if hacked > max_count:
result = [i]
max_count = hacked
elif hacked == max_count:
result.append(i)
print(*result)
이 문제의 핵심은 "역방향 그래프" 만들기 였던 것 같다.문제는 "얼마나 많은 컴퓨터를 해킹할 수 있느냐"이며, 해킹 경로는 B -> A 이기 때문에 B가 해킹되었을 때 B를 신뢰하는 노드들만 보면 돼서 효율적이다.
- graph : 입력된 가로쌍에서 b와 a 포지션을 바꿔서 한 set로 저장한 배열. 배열 인덱스 -> 신뢰받는 노드 숫자, 요소 -> 신뢰하는 노드 숫자 리스트
- while문 : [접근] 항목에 있는 코드와 동일한 bfs 로직
차이점 1. list 대신 deque를 써서 좀 더 빠르고 큐 작업에 용이하도록 변경
차이점 2. 한 노드가 visited 되고, queue에 담길 때마다 count 변수 + 1. graph[current] 배열에는 A 포지션 노드가 들어가 있으므로 i 노드가 해킹될 때 같이 해킹 당하는 노드 숫자를 카운트
- for i in range(1, n+1) : for문으로 순회하며 bfs 실행하고, 노드 하나당 신뢰하는 노드가 몇 개인지 카운트함.
max_count로 최대 A 포지션 노드 수 저장하고, 갱신될 때마다 최고 기록이니 result 배열도 갱신
이렇게 짜면 마지막엔 A 포지션 노드를 가장 많이 가진 노드들만 result 배열에 남게 된다.
나가며
알게된 꿀팁:
무방향 그래프는 노드별로 인접한 모든 노드를 저장하도록 생성
방향이 있는 그래프는 보고 싶은 방향에 있는 노드를 해당 노드의 인덱스 자리에 저장하도록 생성
이제 코드 제출하고 '채점 중'이라는 텍스트에 심장이 미친듯이 뛰기 시작..
'Programming > 백준' 카테고리의 다른 글
| [코테] 백준 11725번 문제 풀이 - 트리 부모 찾기 (0) | 2025.05.18 |
|---|
