[Algorithm] 백준 14502 - 트리의 지름 in Python(파이썬)

💡 백준 14502:

DFS 탐색을 통해 3개의 벽을 세운 새로운 맵을 탐색하고, BFS로 바이러스가 확산되는 너비 확인

🌱 코드 in Python

알고리즘: BFS & DFS

import sys
import copy

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().split())
g = []
for i in range(n):
	g.append(list(map(int, input().split())))

ret = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs():
	global ret
	tmp_g = copy.deepcopy(g) # 원본 그래프가 영향을 받지 않도록 deepcopy
	q = []
	for i in range(n):
		for j in range(m):
			if tmp_g[i][j] == 2:
				q.append((i, j))
	while q:
		cx, cy = q.pop(0)
		for x, y in zip(dx, dy):
			nx = cx + x
			ny = cy + y
			if 0 <= nx < n and 0 <= ny < m and tmp_g[nx][ny] == 0:
				q.append((nx, ny))
				tmp_g[nx][ny] = 2
	tmp = 0
	for i in range(n):
		tmp += tmp_g[i].count(0)
	ret = max(ret, tmp)

def dfs(cnt, x, y):
	if cnt == 3: # 벽이 3개가 되면 
		bfs() # 해당 지도로 바이러스 확산 탐색
		return
	for i in range(x, n):
		for j in range(y, m):
			if g[i][j] == 0:
				g[i][j] = 1
				dfs(cnt + 1, i, j) # 중복된 맵 검사를 피하기 위해 i, j 값 넘기기
				g[i][j] = 0 # 다시 초기화
		y = 0

dfs(0, 0, 0)
print(ret)

그나마 n, m의 최댓값이 작아서 시간초과가 나지 않은 것 같다...
좀 찾아보니 콤비네이션 이런 것도 있던데 나중에 더 찾아봐야지..
오늘은 이걸로도 이미 지쳐버려써,... ㅠ

🧠 기억하자

1. deepcopy!
   • 깊은 복사를 위해서는 copy를 import한 후에 copy.deepcopy(list)같은 형식으로 사용해야 한다

백준 14502 바로가기