[알고리즘][7][백준_1648][Python3] - 격자판 채우기

 

---

문제 이해

백준저지에는 이미 n x m의 격자상에 특정 블록을 넣어 채우는 경우의 수를 구하는 문제들이 많다.

 

2 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 11726번 <2xn 타일링>

https://www.acmicpc.net/problem/11726

2 x N 격자에 2 x 1 , 2 x 2 크기의 타일로 채우는 경우의 수를 구하는 11727번 <2xn 타일링 2>

https://www.acmicpc.net/problem/11727

3 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 2133번 <타일 채우기>

https://www.acmicpc.net/problem/2133

좌우대칭을 고려해야하는 1720번 <타일 코드>

https://www.acmicpc.net/problem/1720

 

위의 타일링 문제들은 기본적인 유형도 있고 조금 응용된 유형도 있으므로 이런 종류의 문제를 한번도 풀어보지 않았다면 위의 문제들을 먼저 풀어보는것을 추천한다.

 

 

이번문제는 보통 격자판의 열의 길이를 고정해주는 여느 타일링 문제들과 다르게 행과 열 모두 1~14칸으로 유동적으로 변화한다.

따라서 n,m에 따른 규칙성을 찾기도 어렵고 n,m이 조금만 늘어나도 값이 커지고 직접구해보기도 까다로운 문제이다.

 

 

---

알고리즘 전략 

먼저 재귀를 이용해 brute-force로 모든 경우의 수를 파악하는 것부터 해보자.

 

칸을 채울때 규칙은 다음과 같이 정의한다.

 

1. [0,0] 에서 타일을 채우기 시작한다.
2. 무조건 아래로 가는방향으로 채운다
    2-1 그 칸을 옆으로 채울경우에는 그다음 아래칸으로 가지만
    2-2 그 칸을 아래로 채울경우에는 아래로 2칸을 먹으므로 두칸 아래로 움직인다
3. 맨 아래 바닥에 도착하면 한칸 오른쪽 맨위로 이동한다.
4. 1-3 과정을 반복하다가 맨 오른쪽칸을 넘어갔을때 타일을 올바르게 채운 경우들의 합을 구한다.

 

위의 규칙을 바탕으로

6 x 6 에서 어떤식으로 채워지는지 보자

 

 

위와같은 격자판에 위 규칙을 이용해 타일을 채운 경우중 한가지이다.

 

타일 위의 번호는 위 규칙에 따라 채워진 순서이다.

위에서아래로 그리고 아래에 도달하면 한칸 오른쪽으로 이동해서 또 아래로...

이 과정이 반복되어 타일들이 모두 채워진것을 알수있다.

 

우리가 첫번째로 해야할 일은 이 과정(brute-force)를 구현하는 것이다.

이과정에서 필자는 열의 개수에 해당하는 n사이즈의 2진수를 이용해서

현재 채우고 있는 행과 그 다음행에서 어느 인덱스가 채워졌고 안채워졌는지를 저장해두었다.

이 과정을 통해 칸을 순회하다가 이미 채워진 칸이면 넘어가고 채워지지 않으면 채우는 방식으로 재귀를 구성하였다.

 

여기까지 하면 작은 수에서는 문제없이 돌아가지만 수가 커지면 단순 brute-force이므로 시간이 매우 오래걸리게 된다.

이미 답을 알고있는(이미 같은 상황에서 가본적이 있는) 구간을 반복적으로 방문하기 때문이다.

 

따라서 메모이제이션을 해주어야하는데 

단순히 현재 인덱스인 [i,j] 만 고려해버리면 안된다.

 

왜냐하면 현재 [i,j]는 같아도 앞으로 채울수있는 칸이 다를수도 있기때문이다.( 위에서 2진수를 이용해서 값을 저장한 이유가 이것이다)

따라서 i,j뿐만 아니라 해당행과 다음행의 칸 정보를 가지고있는 2진수를 모두 사용해서 메모이제이션을 해주어야하는데

이 4가지 변수를 모두 고려하면 아주 좋겠지만 n=14고 m=14 일때 필요한 개수가 14*14*2^14*2*14 이므로 메모리 초과의 위험이 있으므로 이진수 두개중 하나만 이용하는 방법을 이용하면 된다.

 

대신 이렇게 하려면 아무 인덱스에서 막 저장해서는 안되고 맨 위에칸에 방문했을때, 즉 현재 행의 오른쪽 행들이 모두 채울수 있는 비어있는 칸일때 메모이제이션을 이용해주면 된다.

 

 

 

def dp(answer,n,m,i,j,now_state,next_state): # 진행우선방향 : 아래->오른쪽
    tmp1, tmp2 = 0,0
    if(j == m): # 맨 오른쪽 넘었을때
        if(now_state == 1 << n): 
            return 1 # 맨오른쪽을 넘었고 마지막줄을 빈칸없이 다 채웠을때
        else:
            return 0 # 맨오른쪽을 넘었고 마지막줄에 빈칸이 있을때
    if(i == n+1):
        return 0 # 맨 아래 한칸 초과
    if(i == n): # 맨 아래쪽 넘었을때
        now_state = next_state
        next_state = 1<<n
        return dp(answer,n,m,0,j+1,now_state,next_state) # 다음줄로 이동
    else:
        if(next_state == (1<<n) and answer[i][j][now_state] != -1):
            return answer[i][j][now_state]
        if(now_state & 1<<i): # 현재칸이 채워져있다면 다음칸으로 전진
            tmp1 = dp(answer,n,m,i+1,j,now_state,next_state) 
        else:
            tmp1 = dp(answer,n,m,i+1,j,now_state,next_state+(1<<i)) # 옆으로채우기
            if(not(now_state & 1<<(i+1))):
                tmp2 = dp(answer,n,m,i+2,j,now_state,next_state) # 아래로채우기
    total = (tmp1+tmp2)%9901
    if(next_state == (1<<n)):
        answer[i][j][now_state] = total
    return total

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

answer = [[[-1]*(1<<(n+1)) for i in range(m)] for j in range(n)]
now_state = 1 << n
next_state = 1 << n
print(dp(answer,n,m,0,0,now_state,next_state))

 

타일링 문제는 아니지만 이문제를 풀기전에 미리 풀어서 도움이 되었던 문제가 있다.

5721번 <사탕 줍기 대회> 인데

메모이제이션 방법을 떠올리는것이 까다롭다는 점에서 같이 풀어보면 좋은 문제이다.

https://www.acmicpc.net/problem/5721