[Algorithm] 백준 1325 - 효율적인 해킹 in Python(파이썬)

💡 백준 1325:

BFS로 모든 컴퓨터를 순회하며 최장 연결 거리 탐색

🌱 코드 in Python

알고리즘: BFS

import sys
from collections import deque

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

for _ in range(m):
	a, b = map(int, input().split())
	g[b].append(a) # a가 b를 신뢰한다는 것은 결국 b를 해킹하면 a를 해킹할 수 있다는 것이기 때문에 b에 a를 추가

def bfs(i):
	d = deque([i])
	visit = [0] * (n + 1)
	visit[i] = 1
	cnt = 1
	while d:
		i = d.popleft()
		for j in g[i]:
			if not visit[j]:
				d.append(j)
				visit[j] = 1
				cnt += 1
	return cnt

max_cnt = 1
for i in range(1, n + 1): # 컴퓨터 건건으로 탐색
	cnt = bfs(i)
	if cnt > max_cnt: # 최장 길이 갱신
		max_cnt = cnt
		ret = [] # ret 배열 초기화
		ret.append(i)
	elif cnt == max_cnt:
		ret.append(i)

print(*ret)

이번 문제는 단방향으로 연결된 컴퓨터들의 최장 연결 거리를 탐색하는 문제였다

전형적인 BFS & DFS 문제였어서 구현에 어려움은 없었는데,
하 그놈의 시간 초과!!!!! 메모리 초과!!!
정말 짜증나서 죽을 뻔했다 파이썬 버려!!!!

원래 처음에는 아래와 같이 dfs로 코드를 구현했었다

따라서 dfs의 경우
알고리즘: BFS

import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
ret = []

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

def dfs(i):
	global cnt
	visit[i] = 1
	for c in g[i]:
		if not visit[c]:
			cnt += 1
			dfs(c)

max_cnt = 0
for i in range(1, n + 1):
	visit = [0] * (n + 1)
	cnt = 1
	dfs(i)
	if cnt > max_cnt:
		max_cnt = cnt
		ret = []
		ret.append(i)
	elif cnt == max_cnt:
		ret.append(i)

print(*ret)

이 문제의 경우 중요한 점이 컴퓨터 10,000대가 다 연결되어 있을 경우 10,000대에 대하여 10,000번 탐색을 하기 때문에 시간 초과가 나기 쉽다는 것이다

근데 나 최적화 그런거 모르겠고!!!! ㅠ
사람들 다 pypy로 통과하길래 pypy가 먼지도 모르는데 걍 bfs pypy로 통과했다

내 지식이 아주 얕음이 여기서 여실히 드러남 ^^!
어떻게 시간 초과를 줄여야 하는지도 모르겠고 ㅠ
dfs일 때 왜 메모리 초과가 나는지도 진짜진짜 모르겠다

흐 띨빡 ㅠㅠ 아니 덱으로 추가 메모리를 사용하는 bfs가 더 문제 아닌가 ㅠ?
에효 나중에 시간복잡도나 공간복잡도 등에 대해 더 심도있는 이해를 해봐야 할 것 같다

이거 뭐 맨날 감성코딩이야
음~ 대충 느낌 알겠어~ 이러고 넘기니까 안되는 거 아니야!

🧠 기억하자

1. print(*list)
   • 배열 출력 시 원래는 [0, 1, 2, 3, 4]와 같은 형태로 출력되나, *을 붙여주면 0 1 2 3 4와 같이 대괄호와 쉼표를 알아서 떼주고 출력한다 wow

백준 1325 바로가기