2468. 안전영역

그저 최소(최대)만 보면 BFS로 눈돌아가는 나..(언제 정신차릴래)ㅜ

from collections import deque

n = int(input())

graph = [list(map(int, input().split())) for _ in range(n)]

# max 값 찾기(O(n))
max_value = 0
for i in range(len(graph)):
    a = max(graph[i])
    if a > max_value:
        max_value = a

q = deque([(0,0)])

i = 0
count = 1
# 1씩 줄여나가면서 안전 영역 개수 찾기  by BFS
while q:
    x, y = q.popleft()

    value = max_value - i

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

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if ((graph[nx][ny] == graph[x][y]) or
            (graph[nx][ny] <= value) or
            (nx < 0 or nx >= n or ny < 0 or ny >= n)):
            continue

        if ((graph[nx][ny] > value) and )

여기서 풀다가 정신이 나가버렸다.. 

안전구역의 영역을 확인 후에 count+1를 해줘야 하기 때문에, BFS가 아닌 DFS로 접근을 해야 풀이가 수월하다.

 

1. 움직임의 최소단위

2. 안전영역 = 움직임의 최소 단위로 움직이다 자기 자신이 온 1칸을 제외 3면이 막혀있다면 끝, 안전영역 생성

3. 인덱스 밖을 벗어나면 종료

4. 한쪽 방향으로 뻗어나간 움직임을 감지해야 하므로 DFS로 접근을 해야 함.

 

import sys
sys.setrecursionlimit(100000)

# 상, 하, 좌, 우
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# Recursive한 DFS 함수 선언
def dfs(x, y, h):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        
        # 안전영역에 포함되는 조건
        if (0 <= nx < n) and (0 <= ny < n) and not sink_graph[nx][ny] and graph[nx][ny] > h:
           sink_graph[nx][ny] = True
           dfs(nx, ny, h)
           
n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

ans = 1
# 완전 탐색으로 DFS 실행
for k in range(max(map(max, graph))): # 1~최댓값 비교
    sink_graph = [[False]*n for _ in range(n)] # boolean 배열 생성
    count = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not sink_graph[i][j]:
                count += 1
                sink_graph[i][j] = True
                dfs(i,j,k)
        ans = max(ans, count)

print(ans)