TIL 07-19 등산로 조성

김덕협·2026년 7월 19일

TIL

목록 보기

34/41

문제 정보

문제 이름: [모의 SW 역량테스트] 등산로 조성
문제 링크: SWEA 1949번 - 등산로 조성
알고리즘 분류: 그래프 탐색, 깊이 우선 탐색(DFS), 백트래킹, 시뮬레이션

풀이 과정

1 문제 분석 및 제약 조건 확인

핵심 규칙:
1. 등산로는 항상 가장 높은 봉우리에서 시작해야 한다.
2. 다음 칸은 반드시 현재 칸보다 지형의 높이가 낮아야만 이동할 수 있다.
3. 딱 한 번, 최대 $K$ 만큼 지형을 깎아서 높이를 낮출 수 있는 공사 찬스가 주어진다.
제약 조건 및 힌트:
- 지도의 크기 $N$ 이 3 이상 8 이하( $3 \le N \le 8$ )로 극히 작다.
- 최대 공사 가능 깊이 $K$ 도 1 이상 5 이하( $1 \le K \le 5$ )로 매우 제한적이다.
- 이는 모든 경로를 빠짐없이 전부 탐색하는 완전 탐색과 탐색 중 불필요한 경로를 끊거나 원상복구하는 백트래킹을 사용하기에 최적의 조건이다.

2 알고리즘 및 자료구조 선택

자료구조: 2차원 리스트(grid)로 격자형 지도를 표현하고, 방문 여부를 기록할 동일한 크기의 2차원 불리언 리스트(visited)를 사용한다.
알고리즘: 특정 시작점에서 출발하여 만들 수 있는 최대한의 등산로 길이를 연속적으로 탐색해야 하므로 DFS(깊이 우선 탐색)를 선택했다. 한 갈래의 탐색이 끝나면 다른 방향의 탐색에 영향을 주지 않도록 지형 높이와 방문 배열을 원래대로 돌려놓는 백트래킹(Backtracking) 기법이 핵심이다.

3 절차적 구현 흐름

1) 시작점(최고 봉우리) 탐색

맵 전체를 순회하며 가장 높은 지형의 높이(max_v)를 찾는다.
다시 맵을 돌며 max_v와 같은 높이를 가진 모든 좌표를 starting 리스트에 담아둔다.

2) DFS 함수 설계 및 상태 관리

DFS 함수 수행 시 실시간으로 변하는 상태 정보를 매개변수(인자)로 들고 다닌다.

(y, x): 현재 내가 발을 디디고 서 있는 좌표
length: 현재까지 연결된 등산로의 총 길이
bool_shit: 지형을 한 번이라도 깎았는지 여부 (이미 깎았다면 True, 아직 찬스가 있다면 False)

3) 이동 조건 분기와 백트래킹 (핵심 로직)

주변 4방향을 탐색할 때 다음 두 가지 케이스로 분기 처리했다.

Case A. 다음 후보지가 나보다 낮은 경우 (grid[sy][sx] > grid[ny][nx])
- 공사 찬스를 쓸 필요가 없으므로 다음 칸을 방문 처리한 뒤, 현재 공사 상태(bool_shit)를 그대로 토스하며 dfs를 이어간다. 재귀가 끝나면 방문을 해제한다.
Case B. 다음 후보지가 나보다 같거나 높은 경우 (grid[sy][sx] <= grid[ny][nx])
- 아직 공사 찬스를 쓰지 않았다면(not bool_shit), 현재 내 높이보다 딱 1만큼만 낮아지도록 최소한으로 깎는 깊이(min_cut = grid[ny][nx] - grid[sy][sx] + 1)를 계산한다.
- 이 min_cut이 최대 허용치인 K 이하인 경우에만 cut_that_shit을 호출하여 산을 깎고, 찬스 상태를 True로 변경하여 dfs를 재귀 호출한다.
- 탐색 완료 후 돌아 나오면서 깎아놓았던 지형의 높이(-min_cut)와 방문 배열을 반드시 원래대로 되돌려 놓는 백트래킹 처리가 필수적이다.

4 시간 복잡도

최고 봉우리의 개수는 아무리 많아도 $N \times N$ 개(최대 64개)다.
각각의 시작점에서 4방향으로 뻗어나가는 DFS 탐색을 수행한다. 맵의 최대 크기가 $8 \times 8$ 이고 한 번 방문한 칸은 다시 방문하지 않으므로, 하나의 경로에서 최대 깊이는 64를 넘지 못한다.
탐색 중간에 가지치기(공사를 이미 했는데 더 높거나 같은 벽을 만난 경우 등)가 빈번하게 일어나기 때문에, 실제 연산 횟수는 최대 약 수만 번 이내로 제한된다.
따라서 전체 탐색 횟수는 (시작점 개수 $\times$ 각 경로의 DFS 탐색 수)가 되며, 이는 파이썬 기준으로도 제한 시간 2초 내에 아주 여유롭게 통과할 수 있는 수준이다.

💻 최종 정답 코드

def find_starting():
    max_v = -1
    for y in range(N):
        for x in range(N):
            if max_v < grid[y][x]:
                max_v = grid[y][x]
    
    for y in range(N):
        for x in range(N):
            if grid[y][x] == max_v:
                starting.append((y, x))


def cut_that_shit(y, x, k):
    grid[y][x] -= k


def dfs(y, x, length, bool_shit):
    global ans
    
    if ans < length:
        ans = length
    
    sy, sx = y, x
    
    for i in range(4):
        ny, nx = sy + dy[i], sx + dx[i]
        
        if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
            
            # 다음 가려는 후보지가 현재 위치보다 낮은 경우
            if grid[sy][sx] > grid[ny][nx]:
                visited[ny][nx] = True
                dfs(ny, nx, length + 1, bool_shit)
                visited[ny][nx] = False
            
            # 다음 후보지가 현재 위치보다 같거나 높다면?
            elif grid[sy][sx] <= grid[ny][nx]:
                if not bool_shit:
                    min_cut = grid[ny][nx] - grid[sy][sx] + 1
                    
                    if min_cut <= K:
                        cut_that_shit(ny, nx, min_cut)
                        visited[ny][nx] = True
                        dfs(ny, nx, length + 1, True)
                        cut_that_shit(ny, nx, -min_cut)
                        visited[ny][nx] = False
            
# 상 우 하 좌
dx = [0, 1 ,0, -1]
dy = [-1, 0, 1, 0]

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]
    
    starting = []
    find_starting()
    ans = 1
    
    for sy, sx in starting:
        visited[sy][sx] = True
        dfs(sy, sx, 1, False)
        visited[sy][sx] = False
    
    print(f"#{tc} {ans}")