https://www.acmicpc.net/problem/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)
[백준/파이썬]1963 소수 경로 (1) | 2024.01.26 |
---|---|
[백준/파이썬]6236 용돈 관리 (1) | 2024.01.14 |
[백준/파이썬]1967 트리의 지름 (1) | 2023.12.20 |
[백준/파이썬]16234 인구 이동 (0) | 2023.10.16 |
[백준/파이썬]14502 연구소 (1) | 2023.09.26 |