백준 / 실버 1 / 2468. 안전 영역

입력 받기

N = int(input())
grid = [[] for _ in range(N)]
min_height = 100
max_height = 1

# 입력 받기
for i in range(N):
    for val in list(map(int, input().split())):
        grid[i].append(val)
        min_height = min(min_height, val)
        max_height = max(max_height, val)

answer = 0

• 2차원 배열로 입력값을 받는 건 뭐 다른 문제랑 비슷합니다.
• 대신 여기선 각 칸의 높이를 확인해서, 최저 높이(min_height), 최고 높이(max_height)를 계산합니다.
• 내리는 비의 양에 따른 모든 경우를 다 조사할 때...
  • 비가 min_height - 1만큼 내렸을 때부터 (최저 높이보다 적게 비가 왔으니, 아무곳도 잠기지 않음)
  • 비가 max_height만큼 내렸을 때까지 (모든 곳이 잠김)
• 확인하시면 됩니다.
• 문제에서 각 칸의 높이가 $1$, $100$ 사이라 했으니 최댓값으로 $1$, 최솟값으로 $100$을 초기화해 두고, 갱신하면 됩니다.

안전한 영역의 개수 세는 방법

• 이 문제에선 물에 잠기지 않는 칸들이 서로 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있는 영역을 안전한 영역으로 정의합니다.
• 안전한 영역이 총 몇 개인지는 아래와 같은 방법으로 계산할 수 있습니다.
• 일단 현재 height의 높이만큼 비가 왔다고 가정합시다.

1. $N \times N$ 크기의 2차원 배열 checked를 생성

• 안전한 영역의 개수를 세려면 일단 각 칸을 확인해야 하겠죠? 해당 칸을 확인했는지 여부를 체크하는 checked 배열을 만듭니다.
• 물에 잠기지 않은 칸은, 안전한 영역 개수 셀 때 확인해야 하니 False로 둡니다.
• 물에 잠긴 칸은 (grid[i][j] <= height), 추가로 확인할 필요가 없으니 True로 둡니다.

# grid는 각 칸의 높이 정보를, height는 물의 높이를 담은 변수 
# 물에 빠진 칸은 True, 빠지지 않은 칸은 False
checked = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if grid[i][j] <= height:  # 물에 빠진 칸
            checked[i][j] = True

2. checked의 각 원소를 순회

• 우선 안전한 영역의 개수를 나타내는 변수 count를 0으로 초기화합니다.
• 이후 checked 배열의 각 원소를 2차원 반복문으로 순회합니다.
• 이때 원소가 False인 경우, 물에 잠기지 않은 칸이라는 뜻이겠죠?
  • 이제 해당 칸이 속한 안전한 영역의 모든 칸을 True로 바꿔 주고, count에 1을 추가합니다.

🤔 그런데 어떻게 한 영역의 모든 칸을 True로 바꿔 줘요???

• 함수 check_spot(x좌표, y좌표, checked 배열)을 정의합니다. 이 함수의 동작을 설명하자면
• (1) checked 배열의 현 위치 (x좌표, y좌표)를 True로 바꿔줍니다.
• (2) 상하좌우 인접 칸을 확인합니다. 이 때,
  • 인접 칸이 배열의 범위를 벗어나지 않고,
  • 인접 칸이 checked 배열에서 False일 때
  • 해당 인접 위치를 인수로 보내, check_spot()을 재귀 호출합니다.
• 이 과정을 수행하면, 한 영역의 모든 칸이 True로 바뀝니다.

🤔 그런데 상하좌우 인접 칸은 어떻게 확인해요???

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
  
for i in range(4):
    nx, ny = x + dx[i], y + dy[i]		# 상하좌우 인접 칸 확인

• 위 코드의 dx, dy는, 한마디로 상하좌우 중 어디로 갈지 결정하는 역할을 수행합니다.

• for문을 순회하면서 현재 위치 x, y에 dx[i], dy[i]를 더해 nx, ny를 계산합니다.
  • i == 0이면 dx = -1, dy = 0로, (nx, ny)는 위에 있는 칸이 됩니다.
  • i == 1이면 dx = 0, dy = -1로, (nx, ny)는 왼쪽에 있는 칸이 됩니다.
  • i == 2면 dx = 1, dy = 0로, (nx, ny)는 아래에 있는 칸이 됩니다.
  • i == 3이면 dx = 0, dy = 1로, (nx, ny)는 오른쪽에 있는 칸이 됩니다.

최종 코드

# 인접한 물이 차지 않은 칸을 모두 방문 처리
def check_spot(x, y, checked):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    checked[x][y] = True					# 지금 칸은 True로 처리
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]		# 상하좌우 인접 칸 확인
        if 0 <= nx < N and 0 <= ny < N:		# 범위를 안 벗어나는지?
            if not checked[nx][ny]:			# 값이 False인지?
                check_spot(nx, ny, checked) # 재귀 호출
                
count = 0 # 총 안전 영역의 수

# 각 칸을 순회
# 물에 빠지지 않은 칸인 경우, count에 1을 더하고
# check_spot() 사용해 인접 칸을 모두 True 처리
for i in range(N):
	for j in range(N):
		if checked[i][j] == False:
			count += 1
			check_spot(i, j, checked)

시간 복잡도

• 코드가 복잡해 보이지만, 결국에는 checked 배열에 $N^2$개의 칸이 있습니다.
• 배열을 만들고, 모든 칸을 1번씩 체크하면 $O(N^2)$이 소요됩니다.

풀이

• 이제 위 과정을, height가 min_height - 1부터 max_height일 때까지 반복 수행하면 됩니다.
• 가능한 모든 경우를 체크한다... 완전 탐색(브루트포스)의 냄새가 나는군요.

import sys
sys.setrecursionlimit(10**6)

def safe_areas(height):
    # grid는 각 칸의 높이 정보를, height는 물의 높이를 담은 변수 
    # 물에 빠진 칸은 True, 빠지지 않은 칸은 False
    checked = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if grid[i][j] <= height:  # 물에 빠진 칸
                checked[i][j] = True
    
    # 인접한 물이 차지 않은 칸을 모두 방문 처리
    def check_spot(x, y, checked):
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]
        checked[x][y] = True					# 지금 칸은 True로 처리
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]		# 상하좌우 인접 칸 확인
            if 0 <= nx < N and 0 <= ny < N:		# 범위를 안 벗어나는지?
                if not checked[nx][ny]:			# 값이 False인지?
                    check_spot(nx, ny, checked) # 재귀 호출
                    
    count = 0 # 총 안전 영역의 수

    # 각 칸을 순회
    # 물에 빠지지 않은 칸인 경우, count에 1을 더하고
    # check_spot() 사용해 인접 칸을 모두 True 처리
    for i in range(N):
        for j in range(N):
            if checked[i][j] == False:
                count += 1
                check_spot(i, j, checked)
    
    return count

# 입력 받기           
N = int(input())
grid = [[] for _ in range(N)]
min_height = 100
max_height = 1

for i in range(N):
    for val in list(map(int, input().split())):
        grid[i].append(val)
        min_height = min(min_height, val)
        max_height = max(max_height, val)

answer = 0

# 각 높이를 대상으로, 안전 영역의 수를 계산
for height in range(min_height - 1, max_height + 1):
    answer = max(answer, safe_areas(height))
                
print(answer)

• 높이를 인수로 받고 안전한 영역의 개수를 반환하는 safe_areas 함수를 만들었습니다.
• 정답을 담은 변수 answer를 safe_areas 함수의 반환값과 비교해서 갱신하게끔 코드를 짰습니다.
• 그리고 sys.setrecursionlimit(10**6)를 추가했는데요, 재귀가 꽤나 많이 이루어지는 문제라서 최대 깊이를 기본인 $1,000$에서 $10^6$으로 늘려 줄 필요가 있습니다.

시간 복잡도

• 비가 올 수 있는 최대 높이를 $T$, 배열의 행 및 열 수를 $N$으로 둘 때
• safe_areas: 앞서 살펴봤듯이 $O(N^2)$
• safe_areas를 최대 $T$번 반복 -> 최종 $O(T\times N^2)$
• $T \leq 100$, $N \leq 100$이므로 약 $1,000,000$회 연산 수행 -> 1초 안에 충분히 가능

기억할 점

• 2차원 배열에서 장애물 사이의 빈 공간의 수를 구하는 유형의 문제다. 재귀함수를 이용해 각 칸을 탐색하면서, 이미 방문한 칸을 표시할 수 있는 2차원 배열을 함께 관리하면 효과적이다.