2481

경로가 주어지지 않아 스스로 경로를 만들고 최단 경로를 찾아내는 문제이다.

각각의 이진수들 마다 정점으로 생각하고 그 정점과 해밍 거리가 1인 정점들을 연결해야 한다. 기존의 방법들은 간선을 배열에 저장해두기도 하는데 여기서는 정점의 최대 개수가 100000이라 n*n으로는 저장이 안될 것 같아서 정점을 방문 할 때마다 매번 간선을 확인하는 것으로 했다(정점마다 가능한 최대 간선수가 30뿐이라 시간 복잡도에 영향을 주지 않을 것 같기 때문이도 했다)

여기서 이진수를 그대로 가져 갈 것인가? 아니변 변환 할 것인가로 고민을 했는데 다행히 이진수의 최대 길이가 30이므로 int 10진수 값으로 변환했다. 정점을 표현하는데 더 쉬웠다.

특정 정점에서 해밍 거리가 1인 정점이 존재하는지 안하는지를 파악해야한다. 모든 정점을 뒤진다면 O(N)시간이 걸려 모든 정점에서 수행하면 O(N*N)으로 시간초과가 걸릴 것이다. 해결하기 위해서 정점들의 값들을 sort해 binary search를 가능하도록 했다.

binary search를 하기 위해 정점들을 sort한 후에는 기존에 어느 위치에 있었는지를 저장해두어야 했는데 여기서 디버그하는데 상당히 오래걸렸다. 연습장에 예상 결과값을 만들어서 풀었으면 빨랐을 것 같은데 스스로 운에 맡기다가 계속 F10만 눌렀다.

최단 경로의 길이는 다익스트라로 구하면 되고 지나치는 정점 대한 정보는 현재 정점이 이전 정점에 어디를 가리키는지를 각각 저장해두어서 풀었다.

다익스트라, 순회정점, 이진수, 이진탐색이 종합된 문제였다.

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> using namespace std; int d[100005]; int b[100005]; bool visited[100005]; pair<int, int> data[100005]; pair<int, int> origin[100005]; int N, K; int binary(int find){ int lo=0, hi = N; int mid; while(1){ mid=(hi+lo)/2; if(data[mid].first==find) return mid; else if(lo>=hi) break; else if(data[mid].first<find) lo=mid+1; else hi=mid-1; } return -1; } int hamming(int data, int dis){ int up=1; for(int i=0; i<dis; i++) up*=2; if(data&up) data-=up; else data+=up; return data; } int main(){ char s[32]; priority_queue<pair<int, int> > pq; scanf("%d %d", &N, &K); for(int i=0; i<N; i++){ scanf("%s", s); int tmp=0, up=1; for(int piv=K-1; piv>=0; piv--){ if(s[piv]=='1') tmp+=up; up*=2; } d[i]=-1; b[i]=-1; visited[i]=false; origin[i].first=data[i].first=tmp; origin[i].second=data[i].second=i; } d[0]=0; pq.push(make_pair(0, 0)); sort(data, data+N); while(!pq.empty()){ pair<int, int> fro = pq.top(); pq.pop(); int cur_dis = -fro.first; int cur_piv = fro.second; int cur_data = origin[fro.second].first; if(visited[cur_piv]) continue; else visited[cur_piv]=true; for(int i=0; i<K; i++){ int nei = hamming(cur_data, i); int nextIdx = binary(nei); if(nextIdx!=-1){ nextIdx = data[nextIdx].second; if(d[nextIdx]==-1){ d[nextIdx]=cur_dis+1; b[nextIdx]=cur_piv; pq.push(make_pair(-(cur_dis+1), nextIdx)); } else if(d[nextIdx]>cur_dis+1){ d[nextIdx]=cur_dis+1; b[nextIdx]=cur_piv; pq.push(make_pair(-(cur_dis+1), nextIdx)); } } } } int tc, des; scanf("%d", &tc); while(tc--){ stack<int> sta; scanf("%d", &des); des--; sta.push(des); int nextPush = b[des]; while(nextPush!=-1){ sta.push(nextPush); nextPush = b[nextPush]; } if(sta.top()+1!=1){ printf("%d\n", -1); } else{ while(!sta.empty()){ printf("%d ", sta.top()+1); sta.pop(); } printf("\n"); } } return 0; }