이쿼카

I am an amazing Quokka.

4 minute read

1. 문제 내용

  • 문제:

    오늘은 권수쌤이 크기 N \times M인 광산에서 광물을 캐는 부업을 하는 날이다. 광산은 세 가지 종류의 칸으로 구성되어 있다:

    평범한 돌로 이루어진 칸 (이동 가능) 단단한 바위로 이루어진 칸 (이동 불가능) 황금이 묻힌 칸 (이동 가능하며, 지나가면 황금을 1개 얻는다)

    최근 운동을 쉬어 근력이 약해진 권수쌤은 단단한 바위로 이루어진 칸을 통과할 수 없다. 또한 체력도 예전 같지 않아서 항상 오른쪽 또는 아래쪽 방향으로만 이동하기로 했다.

    광산의 가장 왼쪽 위 칸 (1, 1)에서 시작하여, 가장 오른쪽 아래 칸 (N, M)에 도착할 때까지 얻을 수 있는 황금의 최대 개수를 구하시오.

    단, 출발지 (1,1) 혹은 도착지 (N,M)가 단단한 바위로 막혀 있거나, 어떠한 경로로도 도착할 수 없는 경우는 황금을 얻을 수 없으므로 정답은 0이 된다.

  • 입력:

    첫 번째 줄에 광산의 세로 길이 N과 가로 길이 M이 공백으로 구분되어 주어진다. $(1 \leq N \leq 500,\ 1 \leq M \leq 500)$

    두 번째 줄부터 N개의 줄에 걸쳐 각 줄마다 M개의 정수가 공백으로 구분되어 주어진다. 각 정수는 해당 칸의 상태를 나타내며 다음과 같다:

    0: 평범한 돌 (이동 가능, 황금 없음) 1: 단단한 바위 (이동 불가능) 2: 황금이 있는 칸 (이동 가능, 지나가면 황금 1개 획득)

  • 출력:

    권수쌤이 캘 수 있는 황금의 최대 개수를 출력하라.​

2. 문제 유형 파악

해당 문제는 2차원 격자를 이용한 DP 문제입니다. 이 문제가 DP 유형인 이유는 다음과 같습니다.

  1. 문제의 마지막 줄을 보면 “황금의 최대 개수를 구하시오”라고 명시되어 있습니다.
  2. 되돌아 갈 수 없는 단방향 이동 조건

3. 문제를 풀기 위한 핵심 아이디어

이 문제는 전형적인 2차원 격자 탐색 DP(Grid DP) 유형입니다. “오른쪽 또는 아래쪽으로만 이동할 수 있다”는 강력한 제약 조건 덕분에 역방향 사이클이 발생하지 않으며, 이를 이용해 바텀업(Bottom-Up) 방식으로 시작점부터 차근차근 최적값을 누적해 나가는 것이 이 문제를 푸는 핵심입니다.

  1. 상태의 명확한 정의

2차원 배열의 행과 열 인덱스를 광산의 좌표로 삼아 다음과 같이 DP 테이블을 정의합니다.

  • $DP[i][j]$ = 시작점 $(1, 1)$에서 $(i, j)$ 위치까지 도달했을 때 얻을 수 있는 최대 황금 개수
  1. 점화식 세우기

이동 방향이 ‘오른쪽’과 ‘아래쪽’ 단 두 가지뿐입니다. 이를 도착지 입장에서 반대로 생각하면, 현재 위치 (i, j)에 도달하기 위해 방금 거쳐온 이전 칸은 오직 ‘위쪽 칸 $(i-1, j)$’과 ‘왼쪽 칸 $(i, j-1)$’뿐이라는 뜻입니다.
따라서 두 경로 중 더 많은 황금을 들고 온 경로의 값을 선택한 뒤, 현재 칸의 황금을 더해주면 됩니다.

  1. 예외 처리: 단단한 바위(장애물) 차단하기

이 문제에서 가장 꼼꼼하게 설계해야 할 부분은 이동할 수 없는 ‘단단한 바위’의 처리입니다.

  • 시작점과 도착점 원천 차단: 지문의 조건에 따라, 출발지 (1, 1)이나 도착지 (N, M)이 바위로 막혀있다면 경로 자체가 성립하지 않으므로 곧바로 정답을 0으로 출력하고 종료해야 합니다.

4. 코드

import sys

def solve():
    input = sys.stdin.readline

    n, m = map(int, input().split())

    board = [[]]

    #격자 입력을 받아온다
    for _ in range(n):
        row = [0] + list(map(int, input().split()))
        board.append(row)

    #DP 배열을 초기화 시켜준다.
    DP = [[0 for _ in range(m+1)] for _ in range(n+1)]

    #예외 처리인 시작지점과 끝 지점이 막혀있을 경우 출발과 도착을 하지 못하므로 0으로 출력한다
    if board[1][1] == 1 or board[n][m] == 1:
        print(0)
    else:
        for i in range(1, n+1):
            for j in range(1, m+1):

                # 격자에서 해당 칸이 황금이면 위쪽과 왼쪽에서 오는 것 중 큰 값에 +1을 해주고 현재 위치에 그 값을 저장한다.
                if board[i][j] == 2:
                    DP[i][j] = max(DP[i-1][j], DP[i][j-1])+1
                # 격자에서 해당 칸이 이동 가능한 칸이면 위쪽과 왼쪽에서 오는 값중 큰 값으로 업데이트 해준다.
                elif board[i][j] == 0:
                    DP[i][j] = max(DP[i-1][j], DP[i][j-1])
        # 정답이 저장되어 있는 DP[N][M] 값을 출력한다.
        print(DP[n][m])
solve()

5. 복기 및 최적화

문제를 무사히 통과(만점)하긴 했지만, 알고리즘의 견고함과 코드의 가독성을 한 단계 더 고도화(최적화)할수 있는 방안을 복기해 보도록 하겠습니다.

5.1 복기: 잘 설계한 포인트

  • 패딩(Padding) 기법: board와 DP 배열의 크기를 $(N+1) \times (M+1)$로 선언하여, 점화식에서 $i-1$이나 $j-1$을 참조할 때 배열의 인덱스가 음수가 되는 ‘Out of Bounds’ 에러를 조건문 없이 방지했습니다.

  • 초기 예외 차단: 시작점이나 도착점이 바위(1)로 막혀있어 출발조차 못 하는 최악의 케이스를 반복문 진입 전에 미리 쳐내어 불필요한 연산을 막았습니다.

5.2 최적화

  1. 도달 불가 상태의 엄격한 분리(논리적 견고함)

제출한 코드는 바위를 만났을 때(board[i][j] == 1) 아무런 처리를 하지 않아 DP 값이 0으로 유지됩니다.

  • 숨은 위험성:

    만약 테스트 케이스 중에 바위로 막혀 절대 갈 수 없는 길인데, 그 바위 뒤에 황금이 있는 경우가 있다면 코드는 그 칸을 ‘0개의 호아금을 들고 정상적으로 지나온 경로’로 착각하고 황금 개수를 더해버릴 위험성이 있습니다. 만점을 받은 것은 채점 서버의 테스트 케이스에 이런 악랄한 엣지 케이스가 없었기 때문일 확률이 높습니다.

  • 최적화:

    아예 도달할 수 없음을 의미하는 값인 ‘-1`로 DP 배열을 초기화하여, 정상적으로 황금을 0개 얻은 상태(‘0’)와 원천적으로 갈 수 없는 상태(‘-1’)를 엄격하게 분리해야 합니다.

  1. 조건문 단축을 통한 가독성 향상

현재 코드는 현재 칸이 황금(‘2’)일 대와 빈 공간(‘0’)일 때의 점화식을 따로 분리하여 작성했습니다.

  • 최적화:

    두 상태 모두 기존적으로 max(위, 왼쪽) 값을 가져온다는 공통점이 있습니다. 따라서 바위인 경우만 continue로 건너뛰고, 유효한 칸이라면 max값을 가져온 뒤 “현재 칸이 황금일 때만 +1을 해준다”라는 식으로 조건문을 완성하면 중복 코드가 사라지고 훨씬 간결해집니다.

5.3 최적화를 적용한 최종 코드

import sys

def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())

    # 1. 패딩을 포함한 격자 입력
    board = [[0] * (m + 1)]
    for _ in range(n):
        row = [0] + list(map(int, input().split()))
        board.append(row)

    # 2. DP 배열을 -1(도달 불가)로 초기화하여 논리적 허점 차단
    DP = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]

    # 시작 혹은 끝 지점이 막힌 경우 0 출력 후 즉시 종료
    if board[1][1] == 1 or board[n][m] == 1:
        print(0)
        return

    # 시작점 초기화 (시작점에 황금이 있으면 1, 아니면 0)
    DP[1][1] = 1 if board[1][1] == 2 else 0

    # 3. 바텀업 DP 탐색 진행
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 시작점은 덮어쓰지 않도록 건너뜀
            if i == 1 and j == 1:
                continue
            
            # 바위(1)인 경우 갈 수 없으므로 -1 상태 유지
            if board[i][j] == 1:
                continue
            
            # 위쪽 경로와 왼쪽 경로 중 최댓값 탐색
            best_prev = max(DP[i-1][j], DP[i][j-1])
            
            # 위, 왼쪽 모두 도달 불가(-1)가 아니라면 값 갱신
            if best_prev != -1:
                # 중복 코드를 제거하고, 황금(2)일 때만 1을 더해주는 직관적인 로직
                DP[i][j] = best_prev + (1 if board[i][j] == 2 else 0)

    # 4. 정답 출력 (만약 도착지가 최종적으로 -1이라면 길이 없는 것이므로 0 출력)
    print(max(0, DP[n][m]))

if __name__ == '__main__':
    solve()

Comments

You May Also Enjoy