2468 안전 영역

알고리즘 공부

문제 보기

아이디어

비가 올 수 있는 모든 경우에 대하여 안전 영역의 개수를 구한다. DFS, BFS 두 가지 방식으로 안전 영역의 개수를 구할 수 있다.

• DFS를 적용하려면 recursion limit을 늘려줘야 한다.
• 비의 양은 0부터 가장 (높은 지역의 높이-1)까지이다. (잠기는 곳이 한 군데도 없는 경우가 존재하기 때문)

정답 코드

일반적으로 BFS 탐색이 DFS 탐색보다 성능이 우수하다.

BFS

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
Map = [list(map(int, input().split())) for _ in range(n)]
maxHeight = 0
for x in range(n):
    for y in range(n):
        if maxHeight < Map[x][y]:
            maxHeight = Map[x][y]

# BFS 탐색
def bfs(start, t):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    q = deque()
    q.append(start)
    visited[start[0]][start[1]] = True
    while q:
        v = q.popleft()
        for i in range(4):
            x = v[0] + dx[i]
            y = v[1] + dy[i]
            # 연결된 비보다 높고 아직 색칠(방문 처리)하지 않은 지역 색칠
            if x > -1 and x < n and y > -1 and y < n and not visited[x][y] and Map[x][y] > t:
                visited[x][y] = True
                q.append((x,y))

answer = 0
for t in range(maxHeight):
    count = 0
    visited = [[False] * (n) for _ in range(n)]
    for x in range(n):
        for y in range(n):
            # 비의 양보다 높고 아직 조사하지 않은 지역에 대해 안전 영역 색칠(visited=True)
            if Map[x][y] > t and not visited[x][y]:
                bfs((x,y), t)
                count+=1
    if answer < count:
        answer = count

print(answer)

DFS

import sys
input = sys.stdin.readline

# recursion limit 설정
sys.setrecursionlimit(1000000)


n = int(input())
Map = [list(map(int, input().split())) for _ in range(n)]
maxHeight = 0
for x in range(n):
    for y in range(n):
        if maxHeight < Map[x][y]:
            maxHeight = Map[x][y]

# DFS 탐색
def dfs(x,y, t):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    if x < 0 or x >= n or y < 0 or y >= n or Map[x][y] <= t or visited[x][y]:
        return False
    else:
        visited[x][y] = True
        for i in range(4):
            dfs(x+dx[i], y+dy[i], t)
        return True

answer = 0
for t in range(maxHeight):
    count = 0
    visited = [[False] * (n) for _ in range(n)]
    for x in range(n):
        for y in range(n):
            # 안전 영역 하나를 찾을 때마다 count 1 증가
            if dfs(x,y,t): count+=1
    if answer < count:
        answer = count

print(answer)