[Algorithm] 백준 2468 - 안전 영역 in Python(파이썬)

💡 백준 2468:

DFS 탐색을 통해 각 수위마다 연결되지 않는 안전 영역 구하기

🌱 코드 in Python

알고리즘: DFS

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
g = []
max_h = 0
for i in range(n):
	g.append(list(map(int, input().split())))
	max_h = max(max(g[i]), max_h) # 입력받을 시 높이 최대값을 구해놓아야 다 잠기기 전까지의 경우를 셀 수 있음

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

def dfs(i, cx, cy):
	visit[cx][cy] = 1
	for x, y in zip(dx, dy):
		nx = cx + x
		ny = cy + y
		if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and g[nx][ny] > i: # 방문하지 않았고, 안전 영역인 경우
			dfs(i, nx, ny)

ret = 0
for i in range(0, max_h): # 비에 전혀 젖지 않을 경우도 있어서 ^^; 
	visit = [[0] * n for _ in range(n)]
	cnt = 0
	for j in range(n):
		for k in range(n):
			if g[j][k] > i and visit[j][k] == 0:
				dfs(i, j, k)
				cnt += 1
	if cnt > ret:
		ret = cnt

print(ret)

이 문제는 비 수위에 따라 달라지는 안전 영역의 수를 세는 문제였다
근데 문제가 좀 별론게,, 아니 하나로 이어진 많은 땅보다 쪼개진 수가 더 많은 적은 땅이 더 좋다는 건지?!
는.. 각설하고..

그냥 dfs를 수위마다 냅다 돌려주면 된다

나는 입력 받을 때 최대 땅의 높이를 구하는 방식으로 max를 돌렸는데,
set에 넣어서 중복되지 않게 넣고 나중에 for문에서 그 set을 sort하여 돌리면 처음부터 마지막까지 가능한 것 같다

뭐 그런 방법도 있더라~는 그런 이야기.

🧠 기억하자

1. DFS 그만하고 싶다 !!!
   • 왜 아직도 낯설지?

백준 2468 바로가기