전형적인 BFS, DFS 문제이다.
아무래도 1달 동안 알고리즘을 손을 안 대서 기억이 안날 거 같아 일부러 골랐다.
역시나 기억이 잘 나지 않았다.
한 번 제대로 이해해서 그런지 자료 찾아보고 금방 다시 기억이 나서 금방 풀었다.
여기서 주의해야 할 점은 비가 안 올 수도 있다는 것이다.
최근에 내 수준에 맞는 아주 도움이 되는 영상을 보았는데, 이 문제도 시간이 1초 정도인지라 내가 생각한 대로 풀면 시간 초과 나는 거 아니야? 싶었지만 최악의 경우 10^8개가 나올 수 없기 때문에 그냥 높이를 넣기 위한 반복문 + bfs를 사용해서 했다.
from collections import deque
import sys
n = int(input())
dx = [0,0,-1,1]
dy = [-1,1,0,0]
l = []
# 입력
for i in range(n):
l.append(list(map(int,input().split())))
ans = -1 * sys.maxsize # 가장 작은 값을 넣기 위해
def bfs(x, y,h):
q = deque()
q.append([x,y])
global visited
visited[x][y] = True
while q:
node = q.popleft()
xx = node[0]
yy = node[1]
for i in range(4):
global dx, dy
cx = dx[i] + xx
cy = dy[i] + yy
# n * n 넘어가나 안넘어 가나 확인
if cx >= n or cy >= n or cx < 0 or cy < 0:
continue
# 물에 잠기면 패스
if l[cx][cy] <= h:
continue
# 방문노드 확인
if visited[cx][cy]:
continue
visited[cx][cy] = True
q.append([cx,cy])
# 비의 양
for h in range(101):
# 비의 양에 따라 새로운 bfs가 진행되기 때문에 초기화 해줘야 한다.
visited = []
for j in range(n):
visited.append([False] * n)
# bfs 함수에 몇 번 들어갔는지 세는 변수(안전지대 개수)
cnt = 0
for r in range(n):
for c in range(n):
# 방문했다면 패스
if visited[r][c]:
continue
# 물에 잠기면 패스
if l[r][c] <= h:
continue
bfs(r,c,h)
# 함수에 들어갔다 -> 안전지대이다
cnt += 1
ans = max(ans,cnt) # 가장 큰 값을 구하기 위해
print(ans)여기서 중요한 포인트
1. 비의 양에 따라 새로운 방문 배열로 초기화 해줘야 한다.
2. bfs 함수에 몇 번 들어갔나 나오는지(변수 cnt) 이게 즉 안전지대의 개수 이다.
정도만 알고 bfs 개념만 안다면 쉽게 풀 수 있는 문제였다.
아 그리고 파이썬은 가장 작은 정수값은 없고 최대 정수값인 sys.maxsize만 제공하는데 여기 그냥 -1 곱하면 가장 작은 정수값으로 사용 가능하다.
알고리즘을 제대로 이해해야 나중에 다시 할 때 공부하는 시간이 덜 걸린다는 것을 알게 된 시간이었다. 단순히 문제를 풀었냐 마냐에 집중하는 것이 아니라 깊이 있게 이해하는 수준으로 해야겠다.
go-getter