PS Featured

[PS] BOJ 23083 / 꿀벌 승연이

Minjun Kim

07 Dec 2025 • 6 min read

Thumbnail: Photo by Ante Hamersmit (Unsplash)

문제 링크: https://www.acmicpc.net/problem/23083

벌집을 2차원 배열로 표현해봅시다.

풀이

벌집을 2차원 배열료 표현하기

벌집 모양을 컴퓨터 상에서 동일하게 표현할 수는 없으니, 2차원 배열로 바꿔서 표현해야 합니다. 벌집에서는 항상 오른쪽 위 / 오른쪽 아래 / 아래쪽의 3방향으로 이동하지만, 2차원 배열로 표현할 경우 조금 달라집니다.

기존 좌표를 $(r, c)$ ($r$은 행 번호, $c$는 열 번호)라 할 때, 다음에 이동할 수 있는 좌표는 다음과 같습니다.

홀수 열에서 짝수 열로 이동할 때
- 오른쪽 위 $(r-1, c+1)$
- 오른쪽 아래 $(r, c+1)$
- 아래쪽 $(r+1, c)$
짝수 열에서 홀수 열로 이동할 때
- 오른쪽 위 $(r, c+1)$
- 오른쪽 아래 $(r+1, c+1)$
- 아래쪽 $(r+1, c)$

DP

$(1, 1)$에서 출발해 $(N, M)$으로 이동할 수 있는 경로의 수를 세야 합니다. $(N, M)$에서 시작해 어떻게 계산할 수 있는지 알아봅시다.

$(N, M)$으로 도달할 수 있는 경우의 수
= 위쪽에서 내려오는 경우의 수 (기존 방에서 아래로 내려오는 경우)
+ 왼쪽 위에서 내려오는 경우의 수 (기존 방에서 오른쪽 아래로 내려오는 경우)
+ 왼쪽 아래에서 올라오는 경우의 수 (기존 방에서 오른쪽 위로 올라가는 경우)

이는 꼭 마지막 방인 $(N, M)$이 아닌 모든 방에 대해 적용됩니다. 따라서, 전체 문제를 부분 문제로 쪼갤 수 있고 부분 문제의 결과로 전체 문제의 결과를 구할 수 있으므로 DP로 풀 수 있습니다!

점화식 세우기

$(r, c)$로 도달할 수 있는 경우의 수를 점화식을 통해 구해봅시다.

앞서 벌집을 2차원 배열로 변환하면서, 어떤 열에서 출발하는지에 따라 이동할 수 있는 위치가 다릅니다. 배열 번호를 0번부터 사용하기 위해, 홀수 열이라 부르는 열은 $c \mod 2 = 0$이며 짝수 열이라 부르는 열은 $c \mod 2 = 1$인 열입니다.

홀수 열에서 짝수 열로 이동할 때 ($c \mod 2 = 0$)
- 오른쪽 위 $(r-1, c+1)$
- 오른쪽 아래 $(r, c+1)$
- 아래쪽 $(r+1, c)$
짝수 열에서 홀수 열로 이동할 때 ($c \mod 2 = 1$)
- 오른쪽 위 $(r, c+1)$
- 오른쪽 아래 $(r+1, c+1)$
- 아래쪽 $(r+1, c)$

이를 고려해, 현재 좌표 $(r, c)$에 도달할 수 있는 경우의 수를 계산해 봅시다.

현재 열이 짝수 열인 경우 ($c \mod 2 = 1$)
- $(r+1, c-1)$
  - 이전 열에서 오른쪽 위로 이동해 온 경우
- $(r, c-1)$
  - 이전 열에서 오른쪽 아래로 이동해 온 경우
- $(r-1, c)$
  - 이전 열에서 아래로 이동해 온 경우
현재 열이 홀수 열인 경우 ($c \mod 2 = 0$)
- $(r, c-1)$
  - 이전 열에서 오른쪽 위로 이동해 온 경우
- $(r-1, c-1)$
  - 이전 열에서 오른쪽 아래로 이동해 온 경우
- $(r-1, c)$

이전 열에서 아래로 이동해 온 경우

점화식은 다음과 같습니다.

path: int[N][M] = [[0] * M] * N # N행 M열의 2차원 배열

path[1][1] = 1 # 처음 출발점은 항상 1이다.

# (1, 1)에서 (N, M)까지 채워나간다.
for r in 0...N:
  for c in 0...M:
    if c % 2 == 1: # 현재 열이 짝수 열인 경우
      if c - 1 > 0:
        path[r][c] += path[r][c-1] # 이전 열에서 오른쪽 아래로 이동해 온 경우
        
        if r + 1 < N:
          path[r][c] += path[r+1][c-1] # 이전 열에서 오른쪽 위로 이동해 온 경우
      
      if r - 1 > 0:
        path[r][c] += path[r-1][c] # 이전 열에서 아래로 이동해 온 경우
    
    else: # 현재 열이 홀수 열인 경우
      if c - 1 > 0:
        path[r][c] += path[r][c-1] # 이전 열에서 오른쪽 위로 이동해 온 경우
        
        if r - 1 > 0:
          path[r][c] += path[r-1][c-1] # 이전 열에서 오른쪽 아래로 이동해 온 경우
      
      if r - 1 > 0:
        path[r][c] += path[r-1][c] # 이전 열에서 아래로 이동해 온 경우

점화식의 의사 코드

빈 칸 처리하기

벌집의 일부 칸은 비어 있습니다. 따라서, 점화식을 계산하는 과정 중 이전 칸이 빈 칸인지 판단해 빈 칸일 경우 경우의 수를 고려하지 않아야 합니다

전체 코드

input = open(0).readline
MOD = 1_000_000_007

N, M = map(int, input().split())
K = int(input())

path = [[0] * M for _ in range(N)] # 장애물이 있는 칸은 -1, 나머지 칸은 해당 칸에 도달하기 위한 거리가 된다.
# 현재 칸으로 도달할 수 있는 이전 좌표들의 변위
PREV_MOVE = (
    ((0, -1), (-1, -1), (-1, 0)), # 홀수 열로의 이동
    ((1, -1), (0, -1), (-1, 0)), # 짝수 열로의 이동
)

for _ in range(K):
    r, c = map(lambda i: int(i) - 1, input().split()) # 인덱스를 0부터 시작하도록 변환한다.
    path[r][c] = -1 # 장애물 위치를 -1로 표시한다.

path[0][0] = 1 # 처음 출발점은 항상 1이다.

# 배열 번호를 0부터 N-1까지로 사용하기 위해, 열의 홀수/짝수 여부가 반대로 계산된다.
# c % 2 == 0이라면 홀수 열, c % 2 == 1이라면 짝수 열이다.

# (1, 1)에서 (N, M)까지 채워나간다.
for c in range(M):
    for r in range(N):
        if path[r][c] == -1: # 장애물이 있는 칸은 건너뛴다.
            continue
    
    for dr, dc in PREV_MOVE[c % 2]:
        pr = r + dr
        pc = c + dc
        if 0 <= pr < N and 0 <= pc < M and path[pr][pc] != -1:
            path[r][c] = (path[r][c] + path[pr][pc]) % MOD

print(path[N - 1][M - 1])

solution.py