백준 2468 문제 풀이

mauz·2022년 4월 22일

🐒 안전 영역

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

✍ 나의 풀이

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


N = int(input())

matrix = []
for _ in range(N):
  matrix.append(list(map(int, input().split())))

maxpart = 0
level = 0

dx = [-1,0,0,1]
dy = [0,-1,1,0]

def dfs(a,b):
  visited[a][b] = True
  for i in range(4):
    nx = dx[i] + a
    ny = dy[i] + b
    if 0<=nx<N and 0<=ny<N:
      if not visited[nx][ny] and matrix[nx][ny] > level:
        dfs(nx,ny)
  

while True:
  visited = [[False]*(N) for _ in range(N)]
  land = 0
  for i in range(N):
    for j in range(N):
      if not visited[i][j] and matrix[i][j] > level:
        dfs(i,j)
        land += 1
  if land == 0:
    break
  maxpart = max(land,maxpart)
  level += 1

print(maxpart)

문제 이해는 했는데 적절한 풀이가 안떠올라서
자면서 풀이를 그려보고 다음날 문제를 풀었다.

🧠 문제 이해

물에 잠기지 않은 땅끼리 접해있으면 한덩어리로 쳐서 한 개의 안전 영역이 된다.

수위가 0일때부터 모든 땅이 잠길때까지 수위를 1씩 증가시켜

안전 영역이 최대로 발생될 때를 알아보자.

예를 들어

일때

수위가 0일때는 모든 땅이 물에 잠기지 않았고,
1,2,3,4가 한덩어리로, 안전영역이 한 개 이다.

수위가 1일때는 1번 땅이 물에 잠겼고,
2,3,4가 한덩어리로, 안전영역은 한 개 이다.

수위가 2일때는 2번 땅이 물에 잠겼고,
3번 땅 한덩어리, 4번 땅 한덩어리 이므로 안전영역은 두 개 이다.

수위가 3일때는 3번 땅이 물에 잠겼고,
4번 땅 한덩어리가 한개 남았으므로 안전영역은 한 개이다.

수위가 4일때는 4번 땅이 물에 잠겼고,
모든 땅이 물에 잠겨서 안전영역이 존재하지 않으므로 탐색을 종료한다.

위 과정에서 안전영역이 최대였을 때는 두 개 였을 때 이므로,
2를 출력한다.

출력
2

코드

import sys
sys.setrecursionlimit(10**6)  # 재귀 한도 늘리기 

input = sys.stdin.readline	# 입력 빠르게 받기


N = int(input())

matrix = []
for _ in range(N):
  matrix.append(list(map(int, input().split())))

maxpart = 0		# 안전영역이 최대일 때를 저장하는 변수
level = 0		# 수위를 저장하는 변수

# 탐색 방향 상하좌우
dx = [-1,0,0,1]
dy = [0,-1,1,0]

def dfs(a,b):
  visited[a][b] = True	# 방문처리
  for i in range(4):
    nx = dx[i] + a
    ny = dy[i] + b
    if 0<=nx<N and 0<=ny<N:		# matrix 인덱스 벗어나지 않게 범위 설정
      if not visited[nx][ny] and matrix[nx][ny] > level:	#방문 기록이 없고 수위보다 높으면 탐색
        dfs(nx,ny)
  

#모든 땅이 물에 잠길때까지 수위를 1씩 높여 확인하는 while문
while True:
  visited = [[False]*(N) for _ in range(N)]		# 수위가 증가할때마다 다시 탐색하기 위해 방문기록 초기화
  land = 0 # 이번 수위에서의 안전영역 개수를 저장하는 변수 초기화
  
  #모든 칸을 확인하는 이중 for문
  for i in range(N):
    for j in range(N):
      if not visited[i][j] and matrix[i][j] > level:	#방문 기록이 없고 수위보다 높은 땅이면 탐색
        dfs(i,j)
        land += 1	# 이번 수위의 안전영역 한개 추가
  if land == 0:		# 안전영역이 한개도 발견되지 않으면 모두 물에 잠긴것이므로 while문 탈출
    break
  maxpart = max(land,maxpart) #이번 수위에서의 안전영역 개수가 기존 개수보다 많으면 업데이트
  level += 1

print(maxpart) # 안전영역이 최대일때 개수 출력

리팩토링?

for i in range(N):
    for j in range(N):
      	if not visited[i][j] and matrix[i][j] > level:
        	dfs(i,j)
        	land += 1
      	else:
        	visited[i][j] = True