자물쇠( BOJ 1514 )

1514. 자물쇠 : https://www.acmicpc.net/problem/1514

1514번: 자물쇠

 

1. 문제 파악하기

자물쇠는 0~9까지 숫자가 있으며, 총 N개의 디스크로 구성되어 있습니다.

세준이는 한 번에 최대 3개의 디스크를 최대 3칸까지 돌릴 수 있습니다. 이 때, 세준이가 돌려야 할 최소 횟수를 구해야 합니다.

단순히 왼쪽부터 가까운 방향으로 회전해서는 최소 횟수를 구한다는 보장이 없기에 효율적인 탐색 알고리즘이 필요합니다.

 

2. 문제 해결하기

우선, 현재 가장 왼쪽의 자물쇠를 기준으로 최대 3개의 자물쇠를 돌릴 수 있습니다. 이 상태를 배열을 사용해서 표현하면 check[idx][first][second][third](현재 idx번이 가장 왼쪽에 있으며, 그 때의 디스크 번호)와 같이 표현할 수 있습니다.

이렇게 check배열을 만든 다음, 현재 나올 수 있는 경우를 모두 탐색해주면 문제를 효율적으로 해결할 수 있습니다. 다만, 중복된 계산을 없애고, 최소 회전 수를 구해야 하기 때문에 단순히 재귀함수보다는 다른 방식이 필요합니다.

이 때, priority_queue를 사용해주면 편리하게 해결할 수 있습니다. priority_queue를 사용해 지금까지의 회전 수를 기준으로 최소 회전 수를 가진 상태부터 하나씩 추출한 다음, 다음 상태로 하나씩 바꿔주다보면 원하는 비밀번호를 맞추게 됩니다.

 

3. 소스코드

#include <stdio.h>
#include <queue>
#include <vector>
#define NMAX 105
#define LMAX 10
using namespace std;
 
struct Locker {
    int idx, a, b, c;
    int cost;
};
 
int N;
int cur[NMAX], pw[NMAX];
 
int idx, a, b, c, cst;
int aa, bb, cc;
 
int da[3]={1,1,1}, db[3]={0,1,1}, dc[3]={0,0,1};
int check[NMAX][LMAX][LMAX][LMAX];
 
struct cmp {
    bool operator()(Locker a, Locker b) { return a.cost > b.cost; }
};
priority_queue< Locker, vector< Locker >, cmp > pq;
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%1d", &cur[i]);
    for(int i=1;i<=N;i++) scanf("%1d", &pw[i]);
 
    pq.push({1, cur[1], cur[2], cur[3], 0});
    while(!pq.empty()) {
        idx = pq.top().idx;
        a = pq.top().a; b = pq.top().b; c = pq.top().c;
        cst = pq.top().cost;
        pq.pop();
 
        if(idx > N) break;
 
        if(a == pw[idx]) pq.push({idx+1, b, c, cur[idx+3], cst});
        else {
            for(int i=1;i<=3;i++) {
                for(int j=0;j<3;j++) {
                    // 시계방향
                    aa = (a + i*da[j])%LMAX; bb = (b + i*db[j])%LMAX; cc = (c + i*dc[j])%LMAX;
                    if (!check[idx][aa][bb][cc]) {
                        check[idx][aa][bb][cc] = 1;
                        pq.push({idx, aa, bb, cc, cst+1});
                    }
 
                    // 반시계방향
                    aa = (a - i * da[j] + LMAX) % LMAX; bb = (b - i*db[j] + LMAX)%LMAX; cc = (c - i*dc[j] + LMAX)%LMAX;
                    if (!check[idx][aa][bb][cc]) {
                        check[idx][aa][bb][cc] = 1;
                        pq.push({idx, aa, bb, cc, cst+1});
                    }
                }
            }
        }
    }
 
    printf("%d", cst);
}

 

 

 

4. 후기

상태를 변화시키면서 중복된 연산을 제거하는 방식이 다익스트라 알고리즘과 유사했습니다. 동적 프로그래밍이 단순히 재귀함수를 사용하여 메모이제이션을 한다는 생각을 없애줄 수 있는 문제라고 생각합니다.