코드

from collections import deque
import sys
sys.setrecursionlimit(10**9) # DFS 수행 시, 재귀 반복 제한 늘려줌

n = int(input())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))
    
# 새로 배운 문법
# 그래프 전체에서 가장 큰 값을 찾아줌
max_height = max(map(max, graph))

def dfs(x, y, h):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
            
        # 방문한 적이 없고, 즉 아직 침수가 되지 않았고
        # 침수 제한 높이보다 더 높은 경우
        # 방문 처리를 완료하고 DFS 수행
        # 곧 이곳이 안전 지역이다
        if not visited[nx][ny] and graph[nx][ny] > h:
            visited[nx][ny] = True
            dfs(nx, ny, h)

# 최종 정답을 담을 변수
# 최댓값을 구해야 하는데
# 어차피 영역의 수는 0이 최소이므로
# 간단하게 -1로 잡음
answer = -1

# 가장 높은 높이-1까지 반복 수행
# 어차피 가장 높은 지역이 잠기면 안전 지역은 0이다
# k : 설정할 높이
for h in range(max_height):
    
    # 2차원 그래프의 방문 여부를 체크할 리스트
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]
    
    # 각 높이 별 안전 영역의 개수를 담을 변수
    area = 0
    
    # 2차원 배열의 값이 k보다 크고, 아직 방문하지 않은 경우
    # 안전 영역 +1, 방문 처리 완료 후, DFS 수행
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not visited[i][j]:
                area += 1
                visited[i][j] = True
                dfs(i, j, h)
    
    # 이중 for문이 완료된 후 => h에 따른 안전 구역의 개수 계산 완료
    # answer의 값을 업데이트
    # 맨 바깥의 for문이 완료될 때 마다 answer의 값이 갱신
    # 즉, h의 값에 따른 answer의 최댓값을 구할 수 있음
    answer = max(answer, area)
    
print(answer)

문제 해설

그래프 이론 문제.

침수되지 않은 지역의 개수를 구하는 문제이다.

이 문제의 경우, DFS와 BFS 모두 다 사용하여 풀 수 있는 문제. 나의 경우, 단순 구간의 개수를 구하기에 편한 DFS를 사용하였다.

코드 작성에 헷갈렸던 부분은 높이 값 h에 따라서 DFS를 수행하는데, 안전 구역의 개수를 어느 코드 블록에서 늘려줘야 정확한 개수를 구할 수 있는 지에 대한 감을 찾지 못하였다.

# 가장 높은 높이-1까지 반복 수행
# 어차피 가장 높은 지역이 잠기면 안전 지역은 0이다
# k : 설정할 높이
for h in range(max_height):

    # 2차원 그래프의 방문 여부를 체크할 리스트
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]

    # 각 높이 별 안전 영역의 개수를 담을 변수
    area = 0

    # 2차원 배열의 값이 k보다 크고, 아직 방문하지 않은 경우
    # 안전 영역 +1, 방문 처리 완료 후, DFS 수행
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not visited[i][j]:
                area += 1
                visited[i][j] = True
                dfs(i, j, h)

    # 이중 for문이 완료된 후 => h에 따른 안전 구역의 개수 계산 완료
    # answer의 값을 업데이트
    # 맨 바깥의 for문이 완료될 때 마다 answer의 값이 갱신
    # 즉, h의 값에 따른 answer의 최댓값을 구할 수 있음
    answer = max(answer, area)

위와 같이 높이 별 비교를 수행할 때, 이중 for문 안에서 맨 처음 area를 1 증가 시키고 dfs를 수행한 후 다음 반복으로 넘어갈 때 아직도 visited가 False인 구역이 있으면 area를 또 다시 1 증가시키면 된다는 것을 고민 끝에 파악하였다. 그리고 높이 별로 구해지는 안전 영역 area의 최댓값을 구해야 하므로 맨 바깥의 for문이 반복될 때 마다 answer의 값을 업데이트 시켜주면 최종적으로 정답 인정된다.

DFS와 BFS는 어찌보면 코딩 테스의 완전 기초이다. 하지만 이를 응용하기 시작하면 기본적인 틀에서 좀 더 많은 생각을 요구하게 되는 문제가 많은 것 같다. 다양한 문제를 많이 풀어봐야만 당황하지 않고 능수능란하게 풀 수 있다. 많은 연습을 꾸준하게 해서 더 실력을 증진해야겠다.

댓글남기기

참고