📅 2026-05-05 (화)

🎯 오늘 학습한 목표

• A형 기출문제 풀기

문제 정보

• 문제 이름: 암벽 등반 (복원 문제)
• 문제 링크: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZ24OVqqeLvHBIME&contestProbId=AZ3dXmMqIPnHBIPV&probBoxId=AZ24OVqqeLzHBIME&type=USER&problemBoxTitle=%EB%AA%A8%EC%9D%98+SW+%EC%97%AD%EB%9F%89%ED%85%8C%EC%8A%A4%ED%8A%B8+%28A%ED%98%95%29&problemBoxCnt=30
• 알고리즘 분류: 다익스트라

풀이 과정

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

가로 이동의 경우 0이 아니면 못가게 구현하면 되겠지만, 세로 이동의 경우 0이어도 1이 나올 때 까지 끝까지 가봐야한다.

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

heapq를 사용한 다익스트라 알고리즘

3 절차적 구현 흐름

가로 이동 (좌우)의 경우 1이면 가고, 0이면 가지 않는다.
세로 이동의 경우 1이면 가고, 0이라면 1이 나올 때 까지 계속 탐색을 이어간다.

1을 만났다면 difficulty를 비교해서 업데이트 할 지 말지를 결정하고 업데이트 되었다면 queue에 삽입한다.

4 시간 복잡도

정점 수 : O(H * W)
각 정점에서 가로 이동O(1), 세로 이동 시 같은 열을 끝까지 훑는 경우 최악 O(H)
따라서 한 정점당 간선 수는 O(H), 전체 간선 수는 O(N · H) = O(H² · W)
다익스트라 전체 복잡도: O(H² · W · log(H · W))

5 구현한 코드

import heapq
 
def dijkstra(start_y, start_x):
    queue = []
    dist[start_y][start_x] = 0
    heapq.heappush(queue, (dist[start_y][start_x] ,start_y, start_x))
 
    while queue:
        difficulty, sy, sx = heapq.heappop(queue)
         
        if grid[sy][sx] == 3:
            return difficulty
         
        if difficulty > dist[sy][sx]:   # 업데이트 할 필요가 없다면
            continue
         
        # 가로(X좌표)이동
        for dx in [-1, 1]:
            nx = sx + dx
            if 0 <= nx < W and grid[sy][nx] in (1, 3):   # 유효 범위 내 + 받침이라면, 난이도에 변화는 없다 (가로 이동 시에는)
                if dist[sy][nx] > difficulty:
                    dist[sy][nx] = difficulty
                    heapq.heappush(queue, (dist[sy][nx], sy, nx))
             
        # 세로(Y좌표)이동
        for dy in [-1, 1]:
            ny = sy + dy
             
            # 1칸식 이동 성공했다면 난이도는 1이다. 난이도 업데이트는 현재 난이도와 비교해서 더 큰 난이도로 해야함.
            if 0 <= ny < H and grid[ny][sx] in (1, 3):
                cost = 1
                diff = max(cost, difficulty)
                if dist[ny][sx] > diff:
                    dist[ny][sx] = diff
                    heapq.heappush(queue, (dist[ny][sx], ny, sx))
             
            # 빈 공간 이라면
            elif 0 <= ny < H and grid[ny][sx] == 0:
                # 하락 중이었다면
                if dy == 1:
                    for k in range(1, H):
                        k_ny = ny + k
                        if 0 <= k_ny < H and grid[k_ny][sx] in (1, 3):
                            cost = abs(k_ny - sy)
                            diff = max(cost, difficulty)
                            if dist[k_ny][sx] > diff:
                                dist[k_ny][sx] = diff
                                heapq.heappush(queue, (dist[k_ny][sx], k_ny, sx))
                                break
                
                # 상승 중이었다면
                else:
                    for k in range(-1, -H, -1):
                        k_ny = ny + k
                        if 0 <= k_ny < H and grid[k_ny][sx] in (1, 3):
                            cost = abs(k_ny - sy)
                            diff = max(cost, difficulty)
                            if dist[k_ny][sx] > diff:
                                dist[k_ny][sx] = diff
                                heapq.heappush(queue, (dist[k_ny][sx], k_ny, sx))
                                break
                                     
 
INF = float('inf')
T = int(input())
for tc in range(1, T+1):
    W, H = map(int, input().split())    # W는 가로(X좌표), H는 y좌표
    grid = [list(map(int, input().split())) for _ in range(H)]
 
    dist = [[INF] * W for _ in range(H)]

    ans = 0
    found = False
    sy = -1
    sx = -1
    # 시작점 (2 찾기)
    for y in range(H):
        for x in range(W):
            if grid[y][x] == 2:
                sy, sx = y, x
                found = True
                break
        if found:
            break

    ans = dijkstra(sy, sx)
    print(f"#{tc} {ans}")