1. 문제
길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.
우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다.
예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다.
- A=000
- B=111
- C=010
- D=110
- E=001
두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다.
우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A와 C의 해밍 거리가 1이고, 코드 C와 D의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A와 E의 해밍 거리는 1이지만, 코드 E와 B의 해밍 거리가 2이므로 해밍 경로가 아니다.
이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.
https://www.acmicpc.net/problem/2479
2479번: 경로 찾기
길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들
www.acmicpc.net
2. 해결 아이디어
각 숫자들을 노드라고 생각하고, '해밍 거리'를 가지는 노드끼리 연결해준다면 이 문제는 그래프 상에서 최단거리를 찾는 문제로 바뀐다.
주어진 두 노드 사이에서 최단 거리를 찾는 문제이므로 최소신장트리보다는 bfs가 어울린다. (가중치가 없고 시작과 끝이 정해져 있으므로)
대신, bfs를 사용하면 queue에 노드를 넣어야 하는데, 여기서는 경로에 사용된 모든 노드를 출력해야 하므로 queue에는 현재까지 왔던 모든 노드들을 넣어줘야 한다.
+) 풀다가 메모리 초과가 났던 적이 있는데, 처음에는 int형으로 숫자를 받아 이진수를 십진수 형태로 변환해 거리를 계산해줬는데 알고 보니 숫자의 크기가 int, long long int형을 넘어가는 크기라 string으로 입력을 받아야 했었다.
또 경로 전체를 큐에 넣어 돌려야 해서 현재 경로에 갈 수 있는 노드를 하나씩 넣어준 후 queue에 push하고, 넣었던 원소를 다시 빼주는 작업을 처리해야 했었고,
큐에 경로 전체를 저장하다 보니 큐가 조금 무거워지는 느낌이 있었다.
3. 코드
// Baekjoon No. 2479 - 경로 찾기 ?~ 2209
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
int dist(string, string);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k, st, ed, current_node, size;
int i, j;
vector<int> current_path; // saves current_path
cin >> n >> k;
vector<string> codes(n); // code inputs
vector<int> visited(n, 0);
vector<vector<int>> node(n); // relationships of codes
queue<vector<int>> path_queue; // saves node path to queue.
for (i = 0; i < n; i++) {
cin >> codes[i];
}
cin >> st >> ed;
// solving
st--;
ed--;
// 인접 리스트 방식으로 저장
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (dist(codes[i], codes[j]) == 1) {
node[i].push_back(j);
}
}
}
// bfs
path_queue.push({ st });
current_node = st;
while(path_queue.size() > 0) {
current_path = path_queue.front();
current_node = current_path.back();
size = node[current_node].size();
path_queue.pop();
// if found answer
if (current_node == ed)
break;
// if not visited
if (!visited[current_node]) {
visited[current_node] = 1;
// pushing queue
for (i = 0; i < size; i++) {
if (!visited[node[current_node][i]]) {
current_path.push_back(node[current_node][i]);
path_queue.push(current_path);
current_path.pop_back();
}
}
}
}
// output
if (current_node != ed) {
cout << -1;
}
else {
size = current_path.size();
for (i = 0; i < size; i++)
cout << current_path[i] + 1 << " ";
}
return 0;
}
// returns hamming distance of two integers / O(logn)
int dist(string n1, string n2){
int distance = 0, size = n1.length();
for (int i = 0; i < size; i++) {
if (n1[i] != n2[i]) {
distance++;
}
}
return distance;
}4. 배운 점
- 트리에서 최단 거리가 나왔을 때, 다익스트라, 최소신장트리, bfs를 생각하자.
- 인접 리스트 방식으로 트리를 저장해야 메모리 초과를 피할 수 있다.
- 하지만 그러면 가중치가 있을 경우에는 가중치는 따로 이차원 배열을 만들어 저장해줘야 한다.
'알고리즘_PS > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 6549, 1725 - 히스토그램에서 가장 큰 직사각형(C++) (0) | 2022.10.22 |
|---|---|
| [Baekjoon] 2042 - 구간 합 구하기 (C++) (0) | 2022.10.02 |
| [Baekjoon] 1167 - 트리의 지름(C++) (1) | 2022.09.30 |
| [Baekjoon] 1922 - 네트워크 연결 (C++) (1) | 2022.09.30 |
| [Baekjoon] 11725 - 트리의 부모 찾기 (0) | 2022.09.24 |
