[백준/알고리즘] #2468: 안전 영역 [파이썬(python)/DFS/BFS]

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

처음엔 문제를 대충 읽고 단순히 4를 기준으로 물이 잠기고 안 잠기는거를 BFS로 카운트하는 문제인줄 알았다. 

답이 자꾸 다르게 나와서 다시 읽어보니 

'물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. ' 라고 적혀있었다.

 

기존의 BFS문제 구현과 다르게 행열크기만큼 반복문을 "그 최대인 크기"만큼 또 매번 반복문을 돌려줘야하는 로직이었다. 그래서 그래프 해당 인덱스 정보가 0이거나 해당값이었던 다른 문제들과 다르게, "그 최대 크기"에 해당하는지가 조건문이 된다.

이것을 캐치하는게 어려웠다..

 

그 외에는 다른 BFS 문제들과 로직이 비슷하다.

아, visited와 cnt는 매번 "최대의 크기"루프 돌때마다 초기화해줘야한다.

 

파이썬 코드

#2468_안전 영역
import sys
from collections import deque
input = sys.stdin.readline

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

cur_max = 0
for i in range(N):
    for j in range(N):
        cur_max = max(cur_max, graph[i][j])
     
dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

res=0
for k in range(cur_max+1):
    visited = [[0]*N for _ in range(N)]
    res_cnt=[]
    for i in range(N):
        for j in range(N):
            if graph[i][j]>k and visited[i][j]==0:
                res_cnt.append(bfs(i,j,k))
                cnt=0
    res = max(res, len(res_cnt))

print(res)