[Python] BOJ/백준 2468번 안전 영역

[문제]

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

2468번: 안전 영역

 

[풀이]

지역의 높이 정보를 set 으로 모아 어떤 높이의 건물이 있는지 

• 비가 얼마나 오는 지 모르기 때문에 0부터 건물 최고 높이까지 비를 내리게 한다.
• 건물의 높이는 지역의 높이 정보를 set 으로 모아 확인한다.
• 건물 높이보가 현재 내리는 비 높이보다 크고 아직 그 건물을 방문한 적이 없으면
  • count 를 하나 올리고 bfs 함수로 들어간다.
  • 현재 기준이 되는 건물의 상하좌우 에 있는 건물도 아직 방문하지 않았고 건물 높이가 내리는 비 높이보다 크면 큐에 추가한다.
• 큐가 다 돌아 bfs 함수를 나오게 되면 안전한 영역 1개가 생긴 것이다.

 

 

[코드]

import sys
from collections import deque

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


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


N = int(sys.stdin.readline())
region = []
region_value = {0}
for _ in range(N):
    small_region = list(map(int, sys.stdin.readline().split()))
    region_value.update(small_region)
    region.append(small_region)


answer = 0
for k in region_value:
    count = 0
    visited = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if region[i][j] > k and not visited[i][j]:
                count += 1
                bfs(i, j, k)
    answer = max(answer, count)
print(answer)