[백준] 2468번 안전 영역(python)

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

2468번: 안전 영역

 

1. 난이도 실버1 (🥈) 

 

2. 문제 해결 방법

 

rain의 경우 1보다 적게 내리면 아무 지역도 잠기지 않는다.

 

1. 따라서 0부터 1씩 증가하며 map의 value가 잠길 경우 visit, maps를 모두 -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로 안전 영역의 개수를 구하고, rain을 증가시킨다.

 

3. cnt 가 0 이면 (모두 잠겼을 경우) while문을 break 시키고 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 단지번호붙이기 와 비슷한 문제)