https://www.acmicpc.net/problem/2468
2468호: 안전지대
장마철에 대비하여 방재청에서는 다음과 같은 계획을 세우고 있습니다.
먼저 특정 영역의 높이 정보를 파악한다.
그러다가 그 지역에 비가 많이 내리면
www.acmicpc.net
1. 난이도 실버 1 ()
2. 문제 해결 방법
비가 올 경우 강우량이 1 미만이면 침수되는 지역이 없습니다.
1. 따라서 0에 1을 더하고 지도 값이 고정되면 방문과 지도 모두 -1로 변경됩니다.
for i in range(n):
for j in range(n):
if maps(i)(j) <= rain:
maps(i)(j) = -1
visit(i)(j) = -1
2. bfs를 사용하여 안전한 지역의 수를 계산하고 강우량을 늘립니다.
3. cnt가 0(모두 잠김)이면 while 문을 중단하고 cnt의 최대값을 출력합니다.
for i in range(n):
for j in range(n):
if maps(i)(j) !
= -1 and visit(i)(j) == 0:
bfs((i,j))
cnt += 1
rain += 1
if cnt == 0:
break
else:
max_cnt = max(max_cnt, cnt)
print(max_cnt)
3. 내가 작성한 코드
from collections import deque
n = int(input()) #배열의 길이
maps = (list(map(int, input().split())) for _ in range(n))
def bfs(start):
visit(start(0))(start(1)) = 1
queue = ()
queue = deque()
queue.append(start)
dx = (-1,1,0,0)
dy = (0,0,-1,1)
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx(i)
ny = y + dy(i)
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if maps(nx)(ny) !
= -1 and visit(nx)(ny) == 0: #맵이 물에 잠기지 않았고 방문한 적 없는 경우
visit(nx)(ny) = 1
queue.append((nx,ny))
rain = 0
max_cnt = 0
while True:
visit = ((0) * n for _ in range(n)) #매 번 visit는 초기화 시켜줌
cnt = 0
for i in range(n): #rain보다 높이가 낮으면 visit, maps 모두 -1
for j in range(n):
if maps(i)(j) <= rain:
maps(i)(j) = -1
visit(i)(j) = -1
for i in range(n): #전체 maps을 돌며 떨어져있는 안전영역을 찾음
for j in range(n):
if maps(i)(j) !
= -1 and visit(i)(j) == 0:
bfs((i,j))
cnt += 1 # 안전영역의 개수만큼 cnt를 증가시킴
rain += 1
if cnt == 0: #모두 물에 잠길경우 break
break
else:
max_cnt = max(max_cnt, cnt)
print(max_cnt)
BFS/DFS를 배우기 시작하면서 이것을 알아 내려고 노력하고 있습니다.
무엇을 부탁해야할지 모르고 떠났기 때문에 당시에는 문제였습니다.
오늘 주제를 볼 때 간단한 질문은 안전 영역의 수를 찾는 것입니다(백준 2667 복수 및 유사한 질문)