이쿼카

I am an amazing Quokka.

6 minute read

1. 문제 내용

  • 문제:

    헨젤과 그레텔의 계모는 아이들을 숲속에 버리기로 계획했다. 그녀의 계획을 듣게된 헨젤과 그레텔은 집으로 가는 길을 표시하기 위해 하얀 조약돌을 A개 모았다. 계모가 아이들을 데리고 숲속 깊이 들어가는 동안 아이들은 하얀 조약돌을 하나씩 흘렸다. (헨젤과 그레텔은 같은 위치에 조약돌을 중복으로 흘리지 않는다.)

    숲을 이차원 좌표평면으로 표현하자면 현재 헨젤과 그레텔의 위치는 (1,1) 좌표에 해당하고, 그들의 집은 (N,M) 좌표에 해당한다.

    숲에는 바위나 나무 등으로 인해 이동이 불가능한 위치가 B개 존재한다. (불가능한 위치는 중복되지 않는다.) 아이들은 길을 잃지 않기 위해 오직 동쪽(X좌표가 증가함) 혹은 남쪽(Y좌표가 증가함)으로만 이동한다. 숲의 크기 세로 N과 가로 M와 하얀 조약돌의 위치를 의미하는 A개의 (X,Y)좌표와 이동을 방해하는 오브젝트의 위치를 의미하는 B개의 (X,Y)좌표가 주어졌을 때, 하얀 조약돌을 모두 회수하고 집에 돌아오는 경우의 수를 출력하시오.

  • 입력:

    첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다. A는 하얀 조약돌의 개수이고, B는 장애물의 개수이다. 다음 A개의 줄에는 하얀 조약돌의 위치, B개의 줄에는 장애물의 위치가 주어진다.

  • 출력:

    첫째 줄에 경우의 수를 출력한다. 이때, 경우의 수가 21억 이하임이 보장된다.

2. 문제 유형 파악

이 문제는 조건이 추가된 2차원 격자에서의 경로 탐색 문제이며, 해결을 위해 DP와 조합론의 곱의 법칙을 결합해야 하는 유형입니다.

  • DP: 오직 동쪽(x증가)과 남쪽(y 증가)으로만 이동할 수 있다는 제약 조건이 있습니다. 이는 전형적인 바텀업(Bottom-Up) 방식의 2차원 DP 점화식 DP[i][j] = DP[i-1][j] + DP[i][j-1]을 사용할 수 있음을 의미합니다. 또한 N과 M이 최대 100이므로, $O(N \times M)$의 시간 복잡도를 가지는 DP 배열 생성은 메모리와 시간 측면에서 매우 안전합니다.

  • 경유지 분할(Divide and Conquer): 하얀 조각돌을 반드시 모두 회수해야 합니다. 즉 시작 점에서 도착점까지 한 번에 가는 것이 아니라, 조약돌들의 위치를 기점으로 전체 경로를 여러 개의 부분 경로(Sub-path)로 쪼개어 생각해야 합니다.

결론적으로 이 문제는 “필수 경유지가 존재하는 장애물 피하기 DP 문제”로 정의할 수 있습니다.

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

이 문제를 해결하기 위한 로직은 크게 3단계의 아이디어로 전개됩니다.

  1. 필수 경유지(조약돌)의 정렬과 방문 가능성 검증

    조약돌을 모두 회수하기 위해서는 조약돌을 줍는 “순서”가 매우 중요합니다. 주인공은 동쪽(+X)과 남쪽(+Y)으로만 이동할 수 있으므로, 조약돌의 위치 데이터를 X좌표를 1순위, Y좌표를 2순위로 오름차순 정렬해야 합니다.
    정렬을 마친 후에는 반드시 유효성(방문 가능성) 검증을 거쳐야 합니다. 만약 정렬된 조약돌 배열에서 이전 조약돌보다 다음 조약돌의 Y좌표가 더 작다면(예: (2, 4)에서 (3, 2)로 가야하는 경우), 남쪽으로만 가야 하는 규칙을 위반하고 북쪽으로 역주행해야 하므로 해당 숲에서는 조약돌을 모두 줍는 것이 물리적으로 불가능합니다. 그러므로 이러한 경우가 있다면 즉시 0을 출력하도록 처리해야 합니다.

  2. 전체 경로를 여러 개의 독립된 ‘부분 경로’로 쪼개기

    조약돌의 방문 순서가 확정되었다면, 전체 경로는 다음과 같이 여러 개의 독립적인 구간으로 나눌 수 있습니다.

    1. 출발지 (1, 1) -> 첫 번째 조약돌
    2. 첫 번째 조약돌 -> 두 번째 조약돌
    3. …
    4. 마지막 조약돌 -> 도착지 (N, M)

    각 구간별로 이동 가능한 경우의 수를 구한 뒤 모두 곱해주면 최종 정답이 도출됩니다.

  3. 각 구간별 DP 적용 및 장애물 처리

    쪼개진 각 구간의 경우의 수는 2차원 DP를 통해 구합니다.

    • 초기화: DP 배열을 0으로 채우고, 현재 구간의 시작점인 DP[sx][sy] = 1로 설정합니다.

    • 점화식: 시작점부터 도착점까지 반복문을 돌며, 현재 위치가 장애물(B)인 경우 DP[x][y] = 0으로 두고 건너뜁니다. 장애물이 아니라면 위쪽에서 오는 경우와 왼쪽에서 오는 경우를 더해줍니다.

      \[DP[x][y] = DP[x-1][y] + DP[x][y-1]\]
    • 이 계산을 모든 구간에 대해 반복 수행하여 결과값들을 누적 곱셈(Multiply) 처리합니다. 만약 계산 도중 어느 한 구간이라도 도착지(ex, ey)의 경우의 수가 0이 나온다면, 길이 막힌 것이므로 최종 정답도 자연스럽게 0이 됩니다.

4. 코드

import sys

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

    # 세로, 가로, 조약돌의 개수, 장애물의 개수를 입력으로 받기
    n, m, a, b = map(int, input().split())

    stones = []
    obstacles = []

    # 조약돌과 장애물을 입력으로 받아오기
    for _ in range(a):
        stones.append(tuple(map(int, input().split())))

    for _ in range(b):
        obstacles.append(tuple(map(int, input().split())))

    # 조약돌의 위치 정렬 진행
    stones.sort()

    # 시작 지점 (1,1) 부터 조약돌의 위치와 마지막 지점인 (n, m)까지를 하나의 리스트로 묶기
    points = [(1, 1)] + stones + [(n, m)]

    result = 1

    for i in range(len(points)-1):

        sx, sy = points[i] # 현재 지점
        ex, ey = points[i+1] # 다음 조약돌의 지점

        # 만약 다음 조약돌의 지점이 현재 조약돌의 지점보다 x값 혹은 y값이 작을 경우 물리적으로 불가능하기 때문에 0을 출력하고 종료
        if sx > ex or sy > ey:
            print(0)
            return

        # 만약 시작지점 혹은 마지막 지점이 
        if (1, 1) in obstacles or (n, m) in obstacles:
            print(0)
            return
        
        # 현재 지점에서 다음 지점으로의 경우의 수를 기록한 2차원 DP 배열 정의
        DP = [[0] * (ey+1) for _ in range(ex+1)]
        
        # 시작지점의 값을 1로 초기화
        DP[sx][sy] = 1

        for x in range(sx, ex+1):
            for y in range(sy, ey+1):
                
                # 시작지점이면 건너뜀
                if x == sx and y == sy:
                    continue
                
                # 만약 현재 위치에 장애물이 있다면 건너뜀
                if (x, y) in obstacles:
                    continue
                
                # 위에서 오는 경우의 수
                ways_from_top = DP[x-1][y] if x > sx else 0
                
                # 왼쪽에서 오는 경우의 수
                ways_from_left = DP[x][y-1] if y > sy else 0
                
                # 위와 왼쪽에서 오는 경우의 수를 더해서 현재 위치의 DP 배열에 저장
                DP[x][y] = ways_from_left + ways_from_top
        
        # 각 지점별 경우의 수를 곱해줌
        result *= DP[ex][ey]
    
    # 결과 출력
    print(result)

if __name__ == '__main__':
    solve()

5. 복기 및 최적화

5.1 복기

이번 문제는 얼핏 보면 복잡해 보였지만, “필수 경유지(조약돌)”를 기준으로 전체 경로를 여러 개의 독립된 “부분 경로”로 쪼개어 생각하는 것이 핵심이었습니다.

  • 분할 정복과 DP의 결합: 조약돌 좌표를 정렬하여 순서를 확정한 뒤, 시작점 ➔ 조약돌1 ➔ 조약돌2 ➔ 도착점의 각 구간을 독립적인 DP로 계산하고 누적해서 곱해주는(result *= DP[ex][ey]) 아이디어를 코드로 무사히 구현해 냈다.

  • 엣지 케이스 방어: 다음 조약돌의 좌표가 현재 좌표보다 작아 물리적으로 이동이 불가능한 경우(sx > ex or sy > ey)를 0으로 처리해 조기에 종료시키는 예외 처리가 정상적으로 작동하여 만점을 받을 수 있었다.

5.2 최적화 포인트

만점은 받았지만, 코드를 좀 더 최적화할 수 있을지에 대해서 한 번 알아보았다.

  1. list를 set으로 변경하여 탐색 시간 복잡도 축소

현재 코드에서는 장애물을 리스트(obstacles = [])에 담아두고, DP를 계산하는 2중 for문 안에서 if (x, y) in obstacles: 구문을 통해 장애물 여부를 확인하고 있습니다.

  • 문제점: 파이썬에서 list의 in 연산은 리스트의 처음부터 끝까지 하나씩 뒤져보는 선형 탐색을 하므로 시간 복잡도가 $O(B)$(장애물의 개수)입니다. 이를 2중 for문 안에서 매번 실행하면 엄청난 시간 낭비가 발생합니다.
  • 해결책: 장애물 데이터를 해시 테이블 기반인 set자료구조로 받으면 in 연산의 시간 복잡도가 $O(1)$로 획기적으로 줄어든다.
  1. 루프 불변식(Loop Invariant) 외부로 분리

시작 지점이나 도착 지점에 장애물이 있는지 확인하는 코드(if (1, 1) in obstacles or (n, m) in obstacles:)가 구간을 나누는 for문 안에 들어있다.

  • 문제점: 이 조건은 시작점과 끝점에 대한 ‘전역적인’ 검사이므로, 구간을 쪼갤 때마다 매번 확인할 필요가 없다.
  • 해결책: 입력값을 모두 받은 직후, 반복문이 시작되기 전 최상단으로 빼내어 단 한 번만 검사하도록 수정

다음은 최적화가 적용된 코드입니다.

import sys

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

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

    stones = []
    # 최적화 1: 장애물은 O(1) 탐색을 위해 list가 아닌 set으로 선언
    obstacles = set()

    for _ in range(a):
        stones.append(tuple(map(int, input().split())))

    for _ in range(b):
        # set에는 add 메서드 사용
        obstacles.add(tuple(map(int, input().split())))

    # 최적화 2: 전역 예외 처리(시작/도착점 장애물 여부)를 반복문 밖으로 빼내어 1회만 검사
    if (1, 1) in obstacles or (n, m) in obstacles:
        print(0)
        return

    stones.sort()
    points = [(1, 1)] + stones + [(n, m)]

    result = 1

    for i in range(len(points)-1):
        sx, sy = points[i] 
        ex, ey = points[i+1] 

        if sx > ex or sy > ey:
            print(0)
            return
        
        DP = [[0] * (ey+1) for _ in range(ex+1)]
        DP[sx][sy] = 1

        for x in range(sx, ex+1):
            for y in range(sy, ey+1):
                if x == sx and y == sy:
                    continue
                
                # set을 활용한 O(1) 탐색으로 시간 대폭 단축
                if (x, y) in obstacles:
                    continue
                
                ways_from_top = DP[x-1][y] if x > sx else 0
                ways_from_left = DP[x][y-1] if y > sy else 0
                
                DP[x][y] = ways_from_left + ways_from_top
        
        result *= DP[ex][ey]
    
    print(result)

if __name__ == '__main__':
    solve()

Comments

You May Also Enjoy