(백준) 안전지대 2468호(보아구름)

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

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 복수 및 유사한 질문)