JUNGOL/Intermediate_Coder/그래프탐색-BFS/2261 : 경로 찾기

Intermediate_Coder/그래프탐색-BFS/경로 찾기

문제                                            

길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자.

이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 

예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.

 

우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 

예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다. 

 

A=000, B=111, C=010, D=110, E=001 

 

두 코드 와 사이의 해밍 거리를 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이므로 해밍 경로가 아니다. 

 

이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.

 

입력 형식                                     

첫째 줄에는 두 개의 정수 N과 K가 빈칸을 사이에 두고 주어진다(3≤N≤1,000, 2≤K≤30).

둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다. 

하나의 코드는 빈칸이 없이 주어진다. 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다. 

코드가 같은 경우는 없다. 

그 다음 줄에는 해밍 경로를 찾고자 하는 서로 다른 두 개의 코드 A와 B가 각각의 코드번호로 주어진다.

 

출력 형식                                     

입력으로 주어진 두 코드 사이에 해밍 경로가 존재하면

그 경로 중 가장 짧은 경로를 코드 A부터 코드 B까지 경로상의 코드 번호로 출력한다. 

코드 번호를 출력할 경우에는 코드 번호 사이에 하나의 빈칸을 사이에 두고 출력한다. 

만약 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

 

입력 예                                        

5 3
000
111
010
110
001
1 2

 

출력 예                                        

1 3 4 2

---

FindRoute.h

#pragma once
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>

#include "../../Base.h"

using std::queue;
using std::vector;
using std::string;

class FindRoute : public Base
{
protected:
	struct Route
	{
		int index = 0;
		vector<int> route;
		
		Route() {}
		Route(int index) : index(index) { route.push_back(index); }
		Route(int index, const Route& other)
			: index(index)
		{
			for (int otherIndex : other.route)
			{
				route.push_back(otherIndex);
			}
			route.push_back(index);
		}
	};

public:
	virtual void Code() override;

private:
	bool FindHamingRoute();
	bool IsHamingDistance(int index1, int index2);

private:
	int n, k;
	int a, b;

	vector<string> allData;
	queue<Route> q;

	Route result;

	vector<bool> checkList;
};

 

FindRoute.cpp

void FindRoute::Code()
{
	std::cin >> n >> k;

	allData.reserve(n);
	checkList.reserve(n);
	string data;
	for (int i = 0; i < n; i++)
	{
		std::cin >> data;
		allData.emplace_back(data);
		checkList.emplace_back(false);
	}

	std::cin >> a >> b;

	// a, b를 인덱스로 바꿔준다.
	a--; b--;

	if (FindHamingRoute())
	{
		for (int index : result.route)
		{
			std::cout << index + 1 << ' ';
		}
	}
	else
	{
		std::cout << -1;
	}
}

/// <summary>
/// a 번째에서 b로의 경로를 찾는다.
/// </summary>
/// <returns>경로 존재 여부</returns>
bool FindRoute::FindHamingRoute()
{
	q.push(Route(a));
	checkList[a] = true;

	while (q.empty() == false)
	{
		Route curRoute = q.front();
		q.pop();

		for (int i = 0; i < n; i++)
		{
			if(checkList[i] == false && IsHamingDistance(curRoute.index, i))
			{
				Route newRoute(i, curRoute);
				checkList[i] = true;

				if (i == b)
				{
					result = newRoute;
					return true;
				}

				q.push(newRoute);
			}
		}
	}

	return false;
}

/// <summary>
/// 두 코드간의 해밍 여부를 반환한다.
/// </summary>
/// <param name="index1">코드 1의 인덱스</param>
/// <param name="index2">코드 2의 인덱스</param>
/// <returns>해밍 경로인지 여부</returns>
bool FindRoute::IsHamingDistance(int index1, int index2)
{
	int hamingDistance = 0;

	const string& data1 = allData[index1];
	const string& data2 = allData[index2];
	for (int i = 0; i < k; i++)
	{
		hamingDistance += data1[i] ^ data2[i];

		if (hamingDistance > 1)
		{
			break;
		}
	}

	return hamingDistance == 1;
}

 

---

실행 결과 Success(100)

---

 

코드 해설

기본적으로 숫자로 데이터가 들어오긴 하지만 010이나 001 같이 0으로 시작하는 값이 들어오므로 문자로 처리해야 정상적인 결과를 얻을 수 있다.

	vector<string> allData;

 

속도와 공간적 효율성을 위해 데이터를 직접 복사하는 대신 인덱스만 사용하도록 처리한다.

	// a, b를 인덱스로 바꿔준다.
	a--; b--;
...
		Route(int index) : index(index) { route.push_back(index); }
		Route(int index, const Route& other)
			: index(index)
		{
			for (int otherIndex : other.route)
			{
				route.push_back(otherIndex);
			}
			route.push_back(index);
		}

 

해밍 경로를 구하는 건 값이 다를 때 체크하게 되므로 XOR로 비트 연산하면 쉽게 처리할 수 있다.

/// <summary>
/// 두 코드간의 해밍 여부를 반환한다.
/// </summary>
/// <param name="index1">코드 1의 인덱스</param>
/// <param name="index2">코드 2의 인덱스</param>
/// <returns>해밍 경로인지 여부</returns>
bool FindRoute::IsHamingDistance(int index1, int index2)
{
	int hamingDistance = 0;

	const string& data1 = allData[index1];
	const string& data2 = allData[index2];
	for (int i = 0; i < k; i++)
	{
		hamingDistance += data1[i] ^ data2[i];

		if (hamingDistance > 1)
		{
			break;
		}
	}

	return hamingDistance == 1;
}

 

마지막으로 속도 개선을 위해 체크 리스트를 추가한다.

			if(checkList[i] == false && IsHamingDistance(curRoute.index, i))
			{
				Route newRoute(i, curRoute);
				checkList[i] = true;

 

그런데 여기에서 이상한 점이 존재한다. 하나의 아이템을 한 경로에서만 사용할 수 있도록 한다는 점인데, 이렇게 되면 한 번 경로를 선택하면 다른 경로를 체크할 수가 없게 되어 결과적으로 다른 루트로 체크하면 경로가 있을 수 있는 데 그 부분에 대한 체크를 하지 않게 된다.

 

따라서 이건 문제 자체가 틀려먹었다.

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/그래프탐색-BFS/경로 찾기-JUNGOL