[BOJ 8894] Pattern Lock
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8894에서 채점할 수 있습니다.
요약 )
가능한 모든 패턴, 즉, 1,2,...,9 으로 만들 수 있는 모든 순열(중복 허용 X)을 재귀호출로 찾아도 O(9!) 안에 찾을 수 있습니다. 그리고 9! = 362880 입니다. 따라서 이 문제는 모든 패턴을 찾아보면서 입력으로 들어온 그래프와 비교해 보아도 제한 시간을 맞춰 줄 수 있습니다. 문제에서 주어진 예외 사항들을 잘 고려하면서, 재귀호출을 이용하여 모든 패턴을 찾는 프로그램을 구현하면 해결할 수 있습니다. 구현이 핵심인 문제이기 때문에, 코드를 중심으로 봐주시기 바랍니다.
재료 준비 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | // 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)); } } } | cs |
이 풀이에서는 구현의 편의를 위해 이와 같은 재료들을 준비하였습니다.
mid_point[i][j] = i -> j 혹은 j -> i로 갈 때, 거쳐야 할 중간 지점입니다. 중간 지점이 없다면 0을 저장해 놓습니다.
decomp[i][j] = 중간 지점이 있을 경우 i-> 중간지점, 중간지점 -> j 로 i -> j 의 경로를 세분화한 것입니다.
i > j 인 경우는 swap(i,j) 를 하여 처리할 예정이기 때문에 굳이 저장하지 않았습니다.
초기화 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | // 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"); } | cs |
재귀 호출로 답을 찾기 전에 거치는 초기화 과정입니다.
edge_num = 지나야 할 그래프 간선의 개수
is_ans = 답을 찾았는가?
v = 전체 경로를 저장할 벡터
chk[i] = i 가 패턴에 입력되었는가? = v에 i가 포함되어 있는가?
edge[i][j] = i->j 경로를 지날 수 있는가?
edge_chk[i][j] = i>j 경로를 지난 횟수
재귀호출 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | // 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++; } } } | cs |
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--를 하는 식입니다.
최종 코드 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | // 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; } | cs |