안전 영역 [백준 2468]

1. 문제 접근 방법

- BFS, DFS 중에서 파이썬에서는 왠만하면 BFS를 쓰도록 하자

- 이 문제는 visited 배열의 선언이 필요한데, 이 배열을 for문 안에 쓰면 메모리 초과가 발생한다

-> 전역적으로 선언해서 재활용하도록 하자

- 아예 물에 안 잠기는 경우, 즉, maxHeight가 0인 경우가 존재함을 알아야 한다 

 

 

2. 코드

from collections import deque
 
N = int(input())

board = [] 
visited = [[False]*N for _ in range(N)]

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

for i in range(N):
    row = list(map(int, input().split()))
    board.append(row)
    
maxHeight = 0
maxArea = 0 


def dfs(x, y):
    
    visited[x][y] = True
    
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx and nx < N and 0<=ny and ny<N and visited[nx][ny] == False:
            dfs(nx, ny)
    


for i in range(N):
    for j in range(N):
        if board[i][j] > maxHeight:
            maxHeight = board[i][j]
            

def bfs(x, y):
    
    visited[x][y] = True
    q = deque()
    q.append((x, y))
    
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx and nx<N and 0<=ny and ny<N and visited[nx][ny] == False:
                visited[nx][ny] = True
                q.append((nx,ny))
                



for i in range(0, maxHeight+1):
    
    
    area = 0 
    
    visited = [[False]*N for _ in range(N)]
    
    for j in range(N):
        for k in range(N):
            if board[j][k] <= i:
                visited[j][k] = True
    
    
    for j in range(N):
        for k in range(N):
            if visited[j][k] == False:
             area += 1
             bfs(j, k)
             

    maxArea = max(maxArea, area)
    
    
print(maxArea)