[python] 백준 2468번: 안전 영역(BFS)

# 2468 안전 영역

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

2468번: 안전 영역

⭐ 코드

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

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

for i in range(N):
    for j in range(N):
        if graph[i][j] > high:
            high = graph[i][j]

dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()
def bfs(i,j, high):
    queue.append((i,j))
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()

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

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            
            if graph[nx][ny] > high and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx,ny))

result = 0
for k in range(high):
    visited = [[0] * N for _ in range(N)]
    ans = 0

    for i in range(N):
        for j in range(N):
            if graph[i][j] > k and visited[i][j] == 0:
                bfs(i,j, k)
                ans += 1
    
    if result < ans:
        result = ans

print(result)

📝 풀이

처음에는 단순하게 최대 높이로 물에 잠겼을 때 안전 영역의 갯수를 구하는 문제인 줄 알았다. 문제에서 요구하는 것은 최대 높이가 주어졌을 때 그 높이 범위만큼 반복해서 bfs를 실행해 안전 영역이 가장 많을 때를 구하는 문제였다.

 

실버1 문제답지 않게 굉장히 문제를 꼬았다는 느낌이 들었다. 코드의 핵심은 이중 반복문을 통해 최대 높이를 저장 시켜주고, 최대 높이만큼 반복문을 실행시켜서 최댓값을 갱신시켜서 출력하는 문제이다. 

🔓 정답 코드 뜯어보기

from collections import deque

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

for i in range(N):
    for j in range(N):
        if graph[i][j] > high: # 최대 높이값을 저장
            high = graph[i][j]

dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()

N의 크기만큼의 graph를 생성시키주고 이중 반복문을 통해서 최대 높이인 high의 값을 저장시켜준다. graph[i][j]가 high보다 크다면 high에 graph[i][j]를 저장시켜준다. 반복문을 다 돌면 high의 최댓값이 저장되게 된다.

def bfs(i,j, high):
    queue.append((i,j))
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()

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

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            
            if graph[nx][ny] > high and visited[nx][ny] == 0: # 높이보다 크고 방문하지 않은 곳이라면
                visited[nx][ny] = 1 # 방문처리
                queue.append((nx,ny))

높이 범위만큼 실행시켜 줄 bfs를 생성해준다. 여기서 중요한 점이 높이에 따라서 bfs를 계속해서 생성해줘야하므로 탐색 범위를 계속해서 바꿔줘야한다. 이 문제에서 핵심 코드라고 할 수 있는 graph[nx][ny] > high and visited[nx][ny] == 0를 통해서 범위를 잘 설정해주는 것이 핵심이다.

result = 0
for k in range(high):
    visited = [[0] * N for _ in range(N)] # 방문리스트
    ans = 0 # 안전 영역의 갯수

    for i in range(N):
        for j in range(N):
            if graph[i][j] > k and visited[i][j] == 0:
                bfs(i,j, k)
                ans += 1 # 안전 영역 카운트
    
    if result < ans: # 안전 영역의 최댓값 저장시켜주기
        result = ans

print(result)

result라는 변수를 생성해주고 high만큼의 반복문을 돌아준다. 반복문 아래에서 visited와 ans를 생성하는 이유는 bfs를 다 실행시키고 나서 다시 방문리스트를 만들어줘야하기 때문이다. 

 

반복문을 돌면서 graph에서 high의 범위인 k값보다 크고 방문하지 않았던 곳이라면 bfs를 실행시키고 안전 영역을 카운트 해준다. 반복문을 다 돌고 나서는 result와 ans를 비교하면서 result에 최댓값을 저장시켜주고 문제에서 원하는 값인 안전 영역의 최댓값을 출력시켜준다.