백준 2468번 : 안전영역 (Python)

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

def search_safe(n, area, rain) :
    # 찾아낸 안전영역 그룹의 수
    cnt = 0
    # 영역을 탐색했는지 체크하는 배열 (탐색 했음 = 0, 아직 안했음 = 1)
    area_searched = [[1] * n for i in range(n)]
    for i in range(n) :
        for j in range(n) :
            # 아직 탐색하지 않은 안전영역 찾으면 탐색 시작
            if area[i][j] > rain and area_searched[i][j] == 1 :
                cnt += 1
                # 안전영역인지 탐색할 후보 영역의 좌표 목록
                to_search = [[i, j]]
                # 후보 목록에 값이 남아있으면 탐색 계속
                while to_search :
                    # 깊이 우선 탐색
                    i, j = to_search.pop()
                    # 후보 영역의 좌표가 전체 범위에서 벗어났거나 이미 탐색한 영역이면 continue
                    if i < 0 or i >= n or j < 0 or j >= n or area_searched[i][j] == 0 :
                        continue
                    # 후보 영역이 안전영역일때
                    if area[i][j] > rain:
                        # 그 영역과 연결된 영역 탐색 후보 목록에 추가
                        to_search.extend([[i, j-1], [i, j+1], [i-1, j], [i+1, j]])
                    # 해당 영역 탐색했다고 체크
                    area_searched[i][j] = 0
    return cnt

n = int(input())
area = []
for i in range(n) :
    area.append(list(map(int, input().split())))

rain = 1
safe = -1
sol = 1
while safe != 0 :
    safe = search_safe(n, area, rain)
    sol = max(sol, safe)
    rain += 1
print(sol)

DFS는 스택으로도, 재귀로도 구현이 가능한데 아직은 스택이 편하다.

비가 높이 1만큼 올때부터 시작해서 1씩 늘려나가다가, 안정영역의 수가 0(= 모두 잠김)이 되면 while문을 빠져나가 최대값을 출력한다.