[백준] 2468번-(Python 파이썬) - Bfs, Dfs

문제링크 : https://www.acmicpc.net/problem/2468

dfs와 bfs문제는 이제 더이상 다른사람들의 코드를 보지 않아도 혼자 해결할 수 있는
정도로 많이 보았다. 이번 문제는 처음부터 혼자 짜는 와중에 문제가 조금 애매모호한 감이 있어
오래걸렸었다

문제의 빗물의 양...

멍청한 나는 문제를 제대로 이해하지 못해 비가 어느정도 오는지 왜 안적혀있나

한참을 고민했고 랜덤으로 정하란건가라는 생각에 랜덤함수를 사용해 비가 오는 양을
랜덤으로 정하여 풀었었다...

한참을 돌아와 다시 문제를 읽다가 안전영역이 최대로 되는 값을 구하라는걸 이해한 뒤
다시 풀었는데 풀고 나서 희열감보단 다음부턴 문제를 찬찬히 읽어보자라는 생각을 꼭 되세기게 된 문제였다.

bfs를 이용한 코드

from collections import deque
import sys
read = sys.stdin.readline

def dfs(x, y, rain):
  dx = [1, -1, 0, 0]
  dy = [0, 0, -1, 1]

  q= deque()
  q.append([x, y])
  visited[x][y] = 1

  while q:
    a, b = q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0 <= nx < n and 0 <= ny < n and field[nx][ny] > rain and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append([nx, ny])

n = int(read())
field = []

max_list = []

max_num = 0
for _ in range(n):
  field.append(list(map(int, read().split())))

for i in field:
  for j in i:
    if max_num < j:
      max_num = j

for k in range(max_num + 1):
  visited = [[0] * n for _ in range(n)]
  count = 0
  for i in range(n):
    for j in range(n):
      if field[i][j] > k and visited[i][j] == 0: 
        dfs(i, j, k)
        count += 1
  max_list.append(count)

print(max(max_list))

이번 문제의 핵심은
비가 안올때부터 시작해 다 잠길때까지 안전영역의 개수가
최대가 되는 순간을 구해야 한다는걸 캐치하는게 가장 오래 걸렸었던 부분이다.

이 부분만 빨리 캐치한다면 쉽게 풀 수 있다.

dfs로 작성하여 제출을 하면 런타임에러가 자꾸나 더 이상 그만 보고싶어
그냥 bfs로 제출하고 dp알고리즘 공부를 시작하였다.

나중에 다시 공부할 땐 dfs로 꼭 해결해보겠다는 다짐을 하게한 문제였다.