[BOJ 8894] Pattern Lock

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8894에서 채점할 수 있습니다.

요약 )

 가능한 모든 패턴, 즉, 1,2,...,9 으로 만들 수 있는 모든 순열(중복 허용 X)을 재귀호출로 찾아도 O(9!) 안에 찾을 수 있습니다. 그리고 9! = 362880 입니다. 따라서 이 문제는 모든 패턴을 찾아보면서 입력으로 들어온 그래프와 비교해 보아도 제한 시간을 맞춰 줄 수 있습니다. 문제에서 주어진 예외 사항들을 잘 고려하면서, 재귀호출을 이용하여 모든 패턴을 찾는 프로그램을 구현하면 해결할 수 있습니다. 구현이 핵심인 문제이기 때문에, 코드를 중심으로 봐주시기 바랍니다.

재료 준비 )

// code by RiKang, weeklyps.com
#define PII pair<int,int>
 
int mid_point[11][11];
vector<PII> decomp[11][11];
 
void get_midpoint(){
    mid_point[1][3] = 2;
    mid_point[1][7] = 4;
    mid_point[1][9] = 5;
    mid_point[2][8] = 5;
    mid_point[3][7] = 5;
    mid_point[3][9] = 6;
    mid_point[4][6] = 5;
    mid_point[7][9] = 8;
}
 
void get_decomp(){
    for(int i=1; i<=9; i++){
        for(int j=i+1; j<=9; j++){
            if(mid_point[i][j]==0){
                decomp[i][j].push_back(PII(i,j));
                continue;
            }
            decomp[i][j].push_back(PII(i,mid_point[i][j]));
            decomp[i][j].push_back(PII(mid_point[i][j],j));
        }
    }
}
 

 이 풀이에서는 구현의 편의를 위해 이와 같은 재료들을 준비하였습니다. 

  mid_point[i][j] = i -> j 혹은 j -> i로 갈 때, 거쳐야 할 중간 지점입니다. 중간 지점이 없다면 0을 저장해 놓습니다.

  decomp[i][j] =  중간 지점이 있을 경우 i-> 중간지점, 중간지점 -> j 로 i -> j 의 경로를 세분화한 것입니다.

 i > j 인 경우는 swap(i,j) 를 하여 처리할 예정이기 때문에 굳이 저장하지 않았습니다.

초기화 )

// code by RiKang, weeklyps.com
#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace::std;
 
vector<int> v;// 전체 경로를 저장할 벡터
int edge_num; // 지나야 할 그래프 간선의 개수
bool edge[11][11];  // edge[i][j] = i->j 경로를 지날 수 있는가?
int edge_chk[11][11]; // edge_chk[i][j] = i>j 경로를 지난 횟수
bool is_ans;  // 답을 찾았는가?
bool chk[11]; // chk[i] = i 가 패턴에 입력되었는가? = v에 i가 포함되어 있는가?
int mid_point[11][11];
vector<PII> decomp[11][11];
 
void solve(){
    edge_num=0;
    is_ans = false;
    v.clear();
    chk[0] = true;
    for(int i=1; i<=9; i++) chk[i] = false;
    for(int i=1; i<=9; i++) for(int j=1; j<=9; j++)
        edge[i][j] = false, edge_chk[i][j] = 0;
        
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        int v1, v2;
        scanf("%d %d",&v1,&v2);
        if(v1>v2) swap(v1,v2);
        if(v1==v2) continue;
        for(auto p: decomp[v1][v2])
            edge[p.first][p.second] = true;
    }
    
    for(int i=1; i<=9; i++) for(int j=1; j<=9; j++)
        if(edge[i][j])
            edge_num++;
            
    process();
    
    if(!is_ans)
        printf("IMPOSSIBLE\n");
}

 재귀 호출로 답을 찾기 전에 거치는 초기화 과정입니다.

 edge_num = 지나야 할 그래프 간선의 개수

 is_ans = 답을 찾았는가?

 v = 전체 경로를 저장할 벡터

 chk[i] = i 가 패턴에 입력되었는가? = v에 i가 포함되어 있는가?

 edge[i][j] = i->j 경로를 지날 수 있는가?

 edge_chk[i][j] = i>j 경로를 지난 횟수

재귀호출 )

// code by RiKang, weeklyps.com
#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace::std;
 
vector<int> v;
int edge_num;
bool edge[11][11];
int edge_chk[11][11];
bool is_ans;
bool chk[11];
int mid_point[11][11];
vector<PII> decomp[11][11];
 
void process(){
    if(is_ans) return;
    if(edge_num==0 && v.size()>=4){
        for(auto p: v)
            printf("%d ",p);
        printf("\n");
        is_ans = true;
    }
    for(int i=1; i<=9; i++){
        if(v.size()==0){
            chk[i]=true;
            v.push_back(i);
            process();
            chk[i]=false;
            v.pop_back();
        }
        
        if(chk[i]) continue;
        bool con = false;
        int p1 = v.back(), p2 = i;
        if(p1>p2) swap(p1, p2);
        if(!chk[mid_point[p1][p2]]) continue;
        for(auto p: decomp[p1][p2])
            if(!edge[p.first][p.second])
                con = true;
        if(con) continue;
        
        chk[i] = true;
        v.push_back(i);
        for(auto p: decomp[p1][p2]){
            edge_chk[p.first][p.second]++;
            if(edge_chk[p.first][p.second]==1)
                edge_num--;
        }
        
        process();
        
        chk[i] = false;
        v.pop_back();
        for(auto p: decomp[p1][p2]){
            edge_chk[p.first][p.second]--;
            if(edge_chk[p.first][p.second]==0)
                edge_num++;
        }
    }
}

 1. 지나야 할 간선들을 모두 지났고(edge_num==0), 패턴 길이가 4이상이면(v.size()>=4) 답을 찾은 것입니다. (Line 17~22)

-> 답이 아니라면 다음 정점을 찾아야 합니다. (다음 정점 = i)

 2. 첫 위치 설정(v.size()==0)인 경우는 간선이 생성되지 않으므로, 컷팅 없이 재귀를 돌립니다. (Line 24~30)

-> v.size()!=0 일 경우엔 v.back() -> i 의 간선이 생성됩니다.

 3. 이미 해당 위치를 지났거나(chk[i]), 생성되는 간선의 중간 지점이 아직 살아있을 경우(!chk[mid_point[p1][p2]) 컷팅합니다. (Line 32~36)

 4. 생성되는 간선을 지날 수 없을 경우 (입력 그래프에 해당 간선이 없을 경우) 컷팅합니다. (Line 37~40)

 5. 위의 컷팅을 통과한 i는 갈 수 있는 곳이므로 재귀를 돌립니다. 이 때, edge_chk를 이용하여 edge_num을 관리해줘야 합니다. edge_chk[p.first][p.second]이 0에서 1로 바뀌면, 지나야만 하는 간선을 하나 지난 것이므로 edge_num--를 하는 식입니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - G
// BOJ 8894 Pattern Lock
 
#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace::std;
 
vector<int> v;
int edge_num;
bool edge[11][11];
int edge_chk[11][11];
bool is_ans;
bool chk[11];
int mid_point[11][11];
vector<PII> decomp[11][11];
 
void get_midpoint(){
    mid_point[1][3] = 2;
    mid_point[1][7] = 4;
    mid_point[1][9] = 5;
    mid_point[2][8] = 5;
    mid_point[3][7] = 5;
    mid_point[3][9] = 6;
    mid_point[4][6] = 5;
    mid_point[7][9] = 8;
}
 
void get_decomp(){
    for(int i=1; i<=9; i++){
        for(int j=i+1; j<=9; j++){
            if(mid_point[i][j]==0){
                decomp[i][j].push_back(PII(i,j));
                continue;
            }
            decomp[i][j].push_back(PII(i,mid_point[i][j]));
            decomp[i][j].push_back(PII(mid_point[i][j],j));
        }
    }
}
 
void process(){
    if(is_ans) return;
    if(edge_num==0 && v.size()>=4){
        for(auto p: v)
            printf("%d ",p);
        printf("\n");
        is_ans = true;
    }
    for(int i=1; i<=9; i++){
        if(v.size()==0){
            chk[i]=true;
            v.push_back(i);
            process();
            chk[i]=false;
            v.pop_back();
        }
        
        if(chk[i]) continue;
        bool con = false;
        int p1 = v.back(), p2 = i;
        if(p1>p2) swap(p1, p2);
        if(!chk[mid_point[p1][p2]]) continue;
        for(auto p: decomp[p1][p2])
            if(!edge[p.first][p.second])
                con = true;
        if(con) continue;
        
        chk[i] = true;
        v.push_back(i);
        for(auto p: decomp[p1][p2]){
            edge_chk[p.first][p.second]++;
            if(edge_chk[p.first][p.second]==1)
                edge_num--;
        }
        
        process();
        
        chk[i] = false;
        v.pop_back();
        for(auto p: decomp[p1][p2]){
            edge_chk[p.first][p.second]--;
            if(edge_chk[p.first][p.second]==0)
                edge_num++;
        }
    }
}
 
void solve(){
    edge_num=0;
    is_ans = false;
    v.clear();
    chk[0] = true;
    for(int i=1; i<=9; i++) chk[i] = false;
    for(int i=1; i<=9; i++) for(int j=1; j<=9; j++)
        edge[i][j] = false, edge_chk[i][j] = 0;
        
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        int v1, v2;
        scanf("%d %d",&v1,&v2);
        if(v1>v2) swap(v1,v2);
        if(v1==v2) continue;
        for(auto p: decomp[v1][v2])
            edge[p.first][p.second] = true;
    }
    
    for(int i=1; i<=9; i++) for(int j=1; j<=9; j++)
        if(edge[i][j])
            edge_num++;
            
    process();
    
    if(!is_ans)
        printf("IMPOSSIBLE\n");
}
 
int main(){
    get_midpoint();
    get_decomp();
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}