[백준/BOJ] 2468번 : 안전 영역 _Python

2468번: 안전 영역

 

>문제

>접근방법

   비의 양이 정해져있지 않아서 1부터 100까지 다 해보고 안전 영역이 제일 많이 나온 경우의 수를 출력한다. 안전 영역의 개수를 세야하기 때문에 dfs를 사용한다. 지역 전체를 탐색하다가 비의 양보다 높을 경우에만 dfs를 수행하면 된다. 수행될 때마다 temp를 하나씩 더해주고 dfs가 끝난 후에 temp의 개수가 count 보다 클 경우 count를 temp의 값으로 교체한다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

import sys
import copy
# 재귀오류 방지
sys.setrecursionlimit(10**6)

# 인접한 영역 탐색용 인덱스 (0, 0) 기준으로 상하좌우의 좌표
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# 안전 영역 탐색 함수(dfs)
def dfs_rec(x, y, h):
    area[x][y] = 0 # 방문 처리
    
    # 상하좌우 탐색 반복 -> 총 4번
    for i in range(4):
    	# (x, y) 기준으로 상하좌우 인덱스를 a, b에 대입
        a, b = dx[i]+x, dy[i]+y 
        # a와 b가 한 지역의 범위 내에 있으면서 그 영역 높이가 비의 양보다 높은 경우
        if 0 <= a < n and 0 <= b < n and area[a][b] > h:
        	# 인접한 영역의 인접영역을 다시 탐색 (재귀 호출)
            dfs_rec(a, b, h)

# 지역 한 변의 길이 n
n = int(input())
# 결괏값을 담을 변수, 아무 지역도 물에 안 잠길 경우가 있으므로 초기값은 1로 설정한다.
count = 1
# 비의 양
h = 1
# 지역의 높이 정보를 입력받는다.
Area = [list(map(int, input().split())) for _ in range(n)]

# 비의 양이 1부터 100까지 모든 경우 반복
for h in range(1, 101):
	# 깊은 복사(deep copy)->개체 자체를 복사해서 원본을 따로 유지해둔다.
    area = copy.deepcopy(Area)
	# 안전 영역의 개수를 담을 변수
	temp = 0 
    # 지역의 모든 영역 하나씩 탐색
    for j in range(n):
        for k in range(n):
        	# 영역의 높이가 비의 양보다 높은 경우
            if area[j][k] > h:
            	# 인접 영역 탐색
                dfs_rec(j, k, h)
                temp += 1
    # 안전 영역의 개수가 count(초기값:1)보다 클 경우 temp값으로 교체
    if temp > count:
        count = temp
        
# 가장 많은 temp값(안전 영역) 출력
print(count)

 

 

>결과

 

 

>결론 

처음에는 count의 초기값을 0으로 설정해 뒀다. 예제는 다 잘 출력되는데 채점기를 돌리면 70%대에서 틀렸습니다 가 나와서 원인을 알 수가 없었다. 쓰앵님한테 헬프를 요청하니 바로 비에 아무 영역도 잠기지 않을 경우를 집어주셨다. 역시 똑똑하신 쓰앵님