S1 2468. 안전 영역

문제 보기 :  2468번: 안전 영역

---

문제

• 정답률 : 34%

---

작성 코드

from collections import deque

n = int(input())
area = [list(map(int,input().split())) for _ in range(n)]
area_max = max([max(l) for l in area]) # 지형의 최대 높이 계산

# 특정 높이 이하의 영역을 방문 처리하는 함수
def change(graph,num): 
    visited = [[False]*n for _ in range(n)] # 방문 여부를 저장할 2D 리스트
    for i in range(n):
        for j in range(n):
            if graph[i][j]<=num: # 높이가 기준 이하이면 방문 처리
                visited[i][j]=True
    return visited

# BFS를 사용해 연결된 안전 영역을 탐색하는 함수
directions = [(-1,0),(1,0),(0,1),(0,-1)] #상하좌우 방향 설정
def maxsafe(visited,start):
    visited[start[0]][start[1]] = True # 시작 노드를 방문 처리
    dd = deque([start])
    while dd:
        x,y = dd.popleft() # 현재 노드
        for dx,dy in directions:
            xx = x+dx ; yy = y+dy # 다음 노드
            if 0<=xx<n and 0<=yy<n and not visited[xx][yy]:
                visited[xx][yy]=True # 방문 처리
                dd.append((xx,yy))

# 최대 안전 영역의 개수를 계산
answer = 0

# 가능한 모든 높이(0 ~ 최대 높이)
for height in range(area_max+1):
    visited = change(area,height) #  현재 높이 기준으로 방문 처리된 행렬 생성
    area_count = 0 # 현재 높이에서의 안전 영역 개수
    
    for i in range(n):
        for j in range(n):
            if not visited[i][j]: # 방문하지 않은 안전 영역 발견 시
                maxsafe(visited,(i,j)) # 해당 영역 탐색
                area_count += 1 # 영역 개수 증가
    
    answer = max(answer, area_count) # 최대 영역 개수 갱신

print(answer)

---

풀이

이 문제는 주어진 지역의 높이에 따라 물에 잠기지 않은 영역(안전 영역)의 최대 개수를 구하는 문제다.

먼저 지역의 크기와 높이 정보를 입력받고, 지형의 최대 높이를 계산해두었다.

그리고 change 함수를 정의했는데, 이건 area에서 특정 높이 이하인 지역을 방문 처리(물에 잠긴 상태로 변경)해서 2D 방문 배열을 생성하는 함수였다.

다음으로 생성한 maxsafe 함수는 BFS 알고리즘을 사용하는데, 연결된 안전 영역(물에 잠기지 않은 영역)을 탐색하면서, 탐색된 영역은 모두 방문 처리하도록 구성했다.

그리고 답을 찾기 위해서는 모든 높이에 대해 change와 maxsafe를 반복 실행하면서 안전 영역의 개수를 계산했고, 최대 안전 영역 개수를 갱신해 답을 구했다.