[BOJ] 백준 2468 안전 영역

태환·2024년 2월 9일
0

Coding Test

목록 보기
66/151

📌 [BOJ] 백준 2468 안전 영역

📖 문제

📖 예제

📖 풀이

import sys
import copy
sys.setrecursionlimit(10000000)

input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
  graph.append(list(map(int, input().split())))

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

def DFS(x,y):
  tmp_graph[x][y] = 0
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if 0<=nx<N and 0<=ny<N and tmp_graph[nx][ny] > h:
      DFS(nx,ny)

best = 0
for i in range(N):
  for j in range(N):
    best = max(best, graph[i][j])

ans = []
for h in range(best):
  cnt = 0
  tmp_graph = copy.deepcopy(graph)
  for i in range(N):
    for j in range(N):
      if tmp_graph[i][j] > h:
        DFS(i,j)
        cnt += 1
  ans.append(cnt)

print(max(ans))

그래프 내의 최대 값을 찾아내어 그 최대 값의 범위 만큼 DFS/BFS를 수행하여 가장 많은 수행 횟수를 출력한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글