[백준/파이썬]2468 안전 영역

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

2468번: 안전 영역

문제

백준 2468번 안전 영역

 

문제는 

 

빗물의 높이 마다 안전 영역의 개수가 달라질 때, 안전 영역의 개수가 가장 많은 경우의 안전 영역 개수를 출력하는 문제다.

 

문제에는 따로 설명 되어 있지 않지만 읽어보면 빗물의 높이는 0~100까지 가능한 것을 알 수 있다. (처음에 1~100까지로 설정했다가 70%에서 틀렸었다. => 문제 노트에 보면 물에 잠기지 않을 수도 있다고 되어 있다.)

 

DFS로도 풀 수 있을 것 같은데, 나는 BFS로 풀었다.

 

문제 출처를 보니 정보올림피아드 초등부 2번 문제다.. 이런걸 초딩들도 푼다니..

 

문제를 풀기 위해

 

1. 빗물의 높이마다 빗물에 잠긴 영역을 표시한 map을 생성한다. (밑의 코드에서는 rain_map_visit이 이 역할을 한다.)

2. 빗물에 잠기지 않는 위치는 따로 저장한다.

3. 잠기지 않은 위치를 방문 여부를 체크 후 BFS탐색을 통해 안전 영역의 개수를 구한다.

 

이 세 가지를 기반으로 구현하니 정답이 나왔다.

 

BFS는 각 안전 영역에 방문 체크를 하기 위해 사용했다.

정답

import sys
from collections import deque
def bfs() :
    while queue :
        now_c, now_r = queue.popleft()
            
        for dt in range(4) :
            next_c, next_r = now_c + dx[dt], now_r + dy[dt]
            
            if next_c < 0 or next_r < 0 or next_c >= n or next_r >= n :
                continue
            if rain_map_visit[next_c][next_r] == 0 :
                rain_map_visit[next_c][next_r] = 2
                queue.append((next_c, next_r))

input = sys.stdin.readline

n = int(input())
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
map_ = []
ans = 0
for i in range(n) :
    map_.append(list(map(int, input().split())))
for i in range(0, 101) :
    rain_map_visit = [[0 for _ in range(n)] for _ in range(n)]
    
    count = 0
    safe_area = []
    for j in range(n) :
        for k in range(n) :
            if map_[j][k] <= i :
                rain_map_visit[j][k] = 1
            else :
                safe_area.append((j, k))
    for c, r in safe_area :
        queue = deque()
        
        if rain_map_visit[c][r] == 0 :
            count += 1
            rain_map_visit[c][r] = 2
            queue.append((c, r))
            bfs()
    if ans < count :
        ans = count

print(ans)