[BOJ] 안전 영역

---

코드

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

d = [(0,1), (0, -1), (1,0), (-1,0)]
def bfs(h, x, y, visited):
    q = deque([(x,y)])
    visited[x][y] = 1
    while q:
        i, j = q.popleft()
        for dir in d:
            ni, nj = i + dir[0], j + dir[1]
            if 0 <= ni < n and 0 <= nj < n and not visited[ni][nj] and graph[ni][nj] > h:
                q.append((ni, nj))
                visited[ni][nj] = 1
    
    return

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

ans = 0
for h in range(0, 101):
    safe = 0
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and graph[i][j] > h:
                bfs(h, i, j, visited)
                safe += 1
            
    if safe > ans:
        ans = safe

print(ans)

결과

풀이 방법

• bfs 탐색으로 인접한 안전 좌표 중 방문하지 않은 좌표만 큐에 넣고 방문하도록 하였다.

---