[백준/Python] 2468번 - 안전 영역

문제

백준 2468번 - 안전 영역

해결 과정

시행 착오

• 런타임 에러 (RecursionError) ->sys.setrecursionlimit(1000000)
• 이중배열에서 최소, 최대 찾기
  -> min_h = min(map(min, board)) max_h = max(map(max, board))
• 범위: min_h-1,max_h
  • 높이가 최소보다 작을 때의 경우에 최소도 안전영역이 되기 때문에 -1

BFS 풀이

import sys
from collections import deque

n = int(sys.stdin.readline())
board = []

for _ in range(n):
  board.append(list(map(int,sys.stdin.readline().split())))

min_h = min(map(min, board))
max_h = max(map(max, board))
   
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y,h):
  q = deque()
  q.append([x,y,h])
  visited[x][y] = True
  while q:
    a, b,h= q.popleft() 
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0 <= nx < n and 0 <= ny < n:
        if not visited[nx][ny] and board[nx][ny] > h: 
          visited[nx][ny] = True
          q.append([nx,ny,h])
          

max_cnt = 0
for h in range(min_h-1,max_h):
  visited = [[False] *n for _ in range(n)]
  cnt = 0
  for i in range(n):
    for j in range(n):
      if not visited[i][j] and board[i][j] > h:  
        bfs(i,j,h)
        cnt += 1
  if max_cnt < cnt:
    max_cnt = cnt

print(max_cnt)

DFS 풀이

import sys
sys.setrecursionlimit(1000000)
n = int(sys.stdin.readline())
board = []

for _ in range(n):
  board.append(list(map(int,sys.stdin.readline().split())))

min_h = min(map(min, board))
max_h = max(map(max, board))
   
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def dfs(x,y,h):
  visited[x][y] = True
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n:
      if not visited[nx][ny] and board[nx][ny] > h: 
        visited[nx][ny] = True
        dfs(nx,ny,h)

max_cnt = 0
for h in range(min_h-1,max_h):
  visited = [[False] *n for _ in range(n)]
  cnt = 0
  for i in range(n):
    for j in range(n):
      if not visited[i][j] and board[i][j] > h:  
        dfs(i,j,h)
        cnt += 1
  if max_cnt < cnt:
    max_cnt = cnt

print(max_cnt)