문제
입력
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.
출력
첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.
입력 예시 1
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7출력 예시 1
5입력 예시 2
7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9출력 예시 2
6문제 이해
이 문제를 오류 없이 한번에 풀어서 굉장히 기분이 좋았다..!
이 문제는 시뮬레이션과 DFS가 합쳐진 문제이다. 상하좌우로 연결되었으면서 비로 인해 쌓인 물높이보다 높이가 높은 연결된 요소가 몇개인지 카운트하고, 그 중에서 최대값을 찾는다. 그러니까 비로 인해 쌓이는 물높이를 0부터 1씩 올리면서 연결요소의 갯수를 카운트하고 그 중에서 가장 큰 값을 출력하는 방식이다.
비로 인해서 물높이가 1보다 작을 수 있기 때문에 0부터 시작한다. 반복문을 0부터 시작해서 값을 1씩 올린다. end값은 가장 높은 땅의 값을 이용한다.
반복문의 end값 구하기
예제 1을 예로 든다면, 가장 높은 땅은 9이다. 비의 높이가 9까지 차면 모든 부분이 물에 잠기기 때문에 9일때는 어차피 최댓값이 될 수가 없다. 다 잠겨서 연결요소가 0개이다. 그러면 1을 뺀 값이 8까지 반복하면 된다. 그 말은 즉, 가장 높은 땅의 값을 구하고, 거기서 1을 뺀 값을 end로 반복문을 돌리면 된다.
DFS코드
# 백준 2468번 안전 영역
# 재귀 횟수, 읽는 속도 늘리기
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def DFS(y, x):
global visited
visited[y][x] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N and graph[ny][nx] > hight and not visited[ny][nx]:
DFS(ny, nx)
# 0. 입력 및 초기화
N = int(input())
graph = []
count_list = [] # 카운트를 모두 넣어주고 가장 큰 값을 출력할 리스트
# 1. 연결 정보 입력
for i in range(N):
graph.append(list(map(int, input().split())))
# 2. 전체 반복
times = 0
times = max(map(max, graph))
# times는 이차원 리스트에서 가장 큰값
# 0부터 times - 1까지 반복문 돌리면 될듯
# hight는 빗물 높이 (0부터 times-1까지 반복)
for hight in range(times):
# 여기서 visited를 선언해야 높이가 바뀔때마다 초기화 됨
visited = [[False] * N for _ in range(N)]
count = 0
for i in range(N):
for j in range(N):
if graph[i][j] > hight and not visited[i][j]:
DFS(i, j)
count += 1
count_list.append(count)
# 3. 출력
print(max(count_list))visited와 count를 반복문안에서 초기화함으로써 물높이인 hight가 증가할 때마다 초기화가 된다.
알아야할 스킬셋 & 정보
2차원 리스트에서 가장 큰 값을 구하기
최댓값을 구하기 위해서 max()함수를 이용한다. 그 전에 우리는 max()함수가 어떻게 돌아가는지 알아야한다. max()안에 1차원 리스트가 들어가면 그 중에서 가장 큰 값 하나만을 리턴한다. 하지만 이번 문제에서는 2차원 리스트다. max()안에 2차원 리스트를 넣으면, 가장 큰값이 있는 1차원 리스트를 리턴한다.
그러면 총 두번 max함수에 넣으면 가장 큰 값 하나가 리턴 된다. 두번 하기 위해서 map함수를 이용한다.
data = [
[6, 8, 2, 6, 2],
[3, 2, 3, 4, 6],
[6, 7, 3, 3, 2],
[7, 2, 5, 3, 6],
[8, 9, 5, 2, 7]
]
print(max(data)) # 출력: [8, 9, 5, 2, 7]
print(max(map(max, data))) # 출력: 9
BFS코드 - 2024-12-10
# 백준 2468번 안전 영역 BFS풀이
# 입력 속도 늘리기
import sys
input = sys.stdin.readline
# deque import
from collections import deque
# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def BFS(y, x):
global visited, count
queue = deque()
queue.append((y, x))
visited[y][x] = True
while queue:
y, x = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N and graph[ny][nx] > rain_hight and not visited[ny][nx]:
queue.append((ny, nx))
visited[ny][nx] = True
# 0. 입력 및 초기화
N = int(input())
graph = []
visited = [[False] * N for _ in range(N)]
result = 1
# 1. 연결 정보 입력
for i in range(N):
graph.append(list(map(int, input().split())))
# 2. BFS호출
max_value = max(map(max, graph)) # 그래프에서 가장 큰 값 구하기
# 가장 큰 높이 값의 -1 만큼 높이까지 돌리면 될듯
for rain_hight in range(max_value):
visited = [[False] * N for _ in range(N)] # 방문 배열 초기화
count = 0 # 카운트 초기화
for i in range(N):
for j in range(N):
if graph[i][j] > rain_hight and not visited[i][j]:
BFS(i, j)
count += 1
if result < count:
result = count
# 3. 출력
print(result)BFS 한놈만 패기 시작하면서 이 문제도 BFS로 풀었다. DFS로 문제를 풀었을 때 알아야할 스킬셋으로 2차원 리스트의 최댓값 구하기를 다루었다. 시간이 지나고 BFS로 풀기 시작했는데, 예제 입력 넣으면 다 잘 출력이 되는데 틀렸다고만 해서 계속 헤맸다.
이유는 2차원 리스트 최댓값 구하기때문이었다.
# 틀린 코드
max_value = max(max(graph))
# 맞는 코드
max_value = max(map(max, graph))이중으로 쓸때는 map함수를 써야한다. 무의식적으로 map없이 이중구조로 했더니 그냥 정답 값은 잘 출력되는데 백준에서는 틀린 판정을 받는다. 이거 하나때문에 계속 전전긍긍했던 걸 생각하면 참 안타깝다.
틀린 과정
