[백준] 2468.안전 영역 (실버1, Python)

문제

안전 지역은 잠겨있지 않은 지역의 덩어리임!

 

높이 = 4 >> 안전 지역 = 5

높이 = 6 >> 안전 지역 = 4

 

안전역영의 최대 개 : 5

 

 

풀이

2667번 문제에서 약간 조건이 추가된 문제였다. 덕분에 그때 코드 생각해보면서 문제를 풀어봤다.

 

1. 입력값 받기 & 최대 높이 구하기

입력값을 받으면서 변수 m에 최대 값을 저장했다.

비의 양에 대한 조건이 없었고 최대 높이 이상으로 오는건 다 동일한 값이기 때문...!

 

m를 가지고 강수량별 안전 영역 수를 구한다. 

 

 

 

2. 강수량별 안전 영역 개수 확인

비가 안 오는 경우도 생각하여 높이는 0부터 m까지 반복문 실행함.

 

2-1. 변수 설정

아래 변수들은 강수량별로 다른 정보를 가지고 있기에 해당 반복문에 변수를 선언 및 초기화를 진행했다.

• count >> 현재 안전영역 개수
• notrainarr[][] >> 침수 지역 정보 저장
• checkarr[][] >> 방문 기록

 

2-2. 침수 지역 설정

notrainarr 변수에 침수 지역 정보를 저장한다. 침수 지역이 아닐 경우 True 값이 저장된다.

 

2-3. 안전 영역 개수 구하기

2중 반복문을 돌면서 '아직 방문 전인 지역이면서 침수 지역이 아닌 곳'에서 findSafe() 함수를 호출한다.

이때 count 변수에 +1를 더한다. 해당 지역이 하나의 안전영역을 찾았다는 의미이다.

안전 영역의 최대수를 찾아야 하기에 findSafe() 함수 호출 후에 count 값이 result보다 큰 경우에만 result 값을 변경한다.

 

3. 안전 영역 개수 구하기: findSafe() 설명

3-1. 초기 설정

안전영역의 값을 저장할 용도로 큐 변수, q를 선언한다.

q에 안전지역인 x,y 좌표를 저장한다.

checkarr 변수에 count 값을 저장한다. 해당 부분이 안전 영역임을 의미한다. 

 

3-2. 안전영역 개수 구하기

안전영역을 담고 있는 큐를 가지고 반복문을 돌린다.

큐에 있는 원소를 하나 출력하고 이 원소를 기준으로 상하좌우(moveX, moveY 활용)에 있는 지역의 상태를 확인한다.

 

지역의 상태를 확인하기 위해서는 아래와 같은 조건을 만족하여야 한다.

조건1. x,y가 arr 범위값을 넘어가지 않아야 한다.

조건2. 방문 기록이 없는 지역이어야 한다.

조건3. 침수 지역이 아니어야 한다.

 

위의 조건을 만족한 지역은 큐에 x,y좌표를 저장하며 방문 기록을 작성한다.

 

 

최종 코드

import queue

def findSafe(x, y):
    q = queue.Queue() # 한 덩어리 확인
    q.put([x, y])
    checkarr[x][y] = count
    
    while q.qsize() > 0:
        node = q.get()
        # 상하좌우
        moveX = [0, 0, -1, 1]
        moveY = [1, -1, 0, 0]
        
        for i in range(len(moveX)):
            x = node[0] + moveX[i]
            y = node[1] + moveY[i]
            
            # 범위 넘어간 경우
            if x < 0 or y < 0 or x > len(arr)-1 or y > len(arr)-1:
                continue
            
            # 이미 방문한 경우 || 침수 지역인 경우
            if checkarr[x][y] > 0 or not notrainarr[x][y]:
                continue
            
            # 침수 X
            q.put([x, y])
            checkarr[x][y] = count

n = int(input())
arr = [[0]*n for _ in range(n)]

result = 0
m = 0 # 최대 높이

for i in range(n):
    s = input()
    for j in range(n):
        arr[i][j] = int(s.split(" ")[j])
        if arr[i][j] > m : m = arr[i][j]

for h in range(m):
    count = 0 # 안전지역 개수
    notrainarr = [[False]*n for _ in range(n)] # 침수 지역
    checkarr = [[0]*n for _ in range(n)] # 방문 확인
    
    # 침수 지역 구분
    for i in range(n):
        for j in range(n):
            # 침수 지역 X : True
            if h < arr[i][j]: notrainarr[i][j] = True
            
    for xi in range(n):
        for yi in range(n):
            # 방문 전 && 침수 X
            if checkarr[xi][yi] == 0 and notrainarr[xi][yi]:
                count+=1
                findSafe(xi, yi)
                if count > result: result = count
                
print(result)

 

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