안녕하세요. DevJunku입니다.
오늘은 2468 안전 영역 문제를 풀어보려고 해요. 가장 대표적인 BFS 문제이구요. 상 하 좌 우 델타 이동을 활용한 Queue를 이용하면 금방 문제를 풀 수 있습니다.
문제가 어려운 편은 아니었습니다. 요새 알고리즘을 좀 뜸하게 풀어서 다시 머리좀 코드를 좀.. 썼습니다..ㅋㅋ 약간 풀이 방법들을 외워서 푸는 문제들은 쉽게 쉽게 접근할 수 있는 장점이 있다보니, 가끔씩 심심할 때 풀어본답니다. 그럼 시작
문제 설명에서 알 수 있듯이 장마철이라고 했지, 장마철로 비가 얼마나 왔는지는 안알려줬습니다. 입력값으로 장마로 인해 나올 수 있는 빗물의 양은 높이는 1이상 100 이하의 정수이다. 라는 건데요. 그냥 100번 반복해서 가장 영역이 많이 드러난 부분만 찾아주면 됩니다. 그러다 보니 100번의 연산은 무조건 들어가고 그때마다 2차원 배열의 원소를 모두 체크해주어야 합니다. 그리고 무엇보다 문제의 배열을 입력 받으시고 얘를 이용한 방문 배열을 매 분기마다 만든신 후 이 방문 배열을 이용해서 BFS를 돌리면 되요. 물에 잠기지 않은 지역이면서 이동이 가능한 지역은 같은 지역이니, 한 번도 방문 안된 원소에서 갈 수 있는 상 하 좌 우 를 체크하면서 영역의 개수를 세어주면 됩니다. 물론1 영역의 개수는 BFS를 시행한 횟수가 되겠지요!
그리고 마지막으로 출력값은 가장 많은 영역의 개수이니 배 분기마다 영역의 개수를 저장해주시고 최종적으로 정답 내릴 수에 Update 시켜주시면 바로 문제가 풀립니다. 제가 작성한 코드는 다음과 같습니다.
from collections import deque
# deque를 사용하는 이유는 시간 복잡도를 줄이기 위해서입니다.
# pop(n)은 시간복잡도가 O(n)이지만 deque의 popleft()는 시간 복잡도가 O(1)입니다.
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def bfs(x, y): # BFS 체크
queue = deque([(x, y)])
while queue:
cx, cy = queue.popleft()
for dx, dy in d:
nx, ny = cx + dx, cy + dy
if 0 <= nx < n and 0 <= ny <n:
# 새로 계산한 인덱스가 배열 범위에 있는지 체크
if not visited[nx][ny]:
# 방문하지 않았다면, 방문!
visited[nx][ny] = True
queue.append((nx, ny)) 그러면서 queue에 저장
final_cnt = 0 # 최종 답
for i in range(1, 101): # 문제 요구로 인해 100번 순회
repeat_cnt = 0 # 하나의 반복으로 인해 매번 영역 개수를 표기하기 위한 변수 매번 0으로 초기화
visited = [[False for _ in range(n)] for _ in range(n)] # 방문 배열
for j in range(n):
for k in range(n):
if arr[j][k] < i:
visited[j][k] = True # 비로 인해 잠긴 부분은 방문하지 않아야 해서 방문 배열에서 방문했다고 표시
for i in range(n):
for j in range(n):
if not visited[i][j]: # 다시 돌면서 bfs를 사용
repeat_cnt += 1 # 이 때 마다 영역의 개수를 세어줌
bfs(i, j)
if repeat_cnt > final_cnt: # 영역의 최대값을 구하기 위한 부분
final_cnt = repeat_cnt
print(final_cnt) # 마지막으로 출력!끝!
