백준 2479 - 경로 찾기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2479

2479번: 경로 찾기

 

저는 2가지 방법으로 접근해서 풀었습니다.

1. 현재 지점에서 모든 이진 코드를 확인해, 1개가 차이날 경우 해당 지점을 탐색한다.

2. 모든 이진 코드를 1의 갯수로 나눈 뒤, 1의 갯수가 1개 차이나는 곳만 확인한다. 

첫번째 방법은 짜기 쉬운 대신에 시간이 오래 걸렸고, 두번째 방법은 복잡했던 대신에 시간이 짧았습니다. 

 

먼저 첫번째 방법부터 설명하겠습니다.

이진 코드를 string을 이용해 입력받았습니다. -> 서로 다른 자리를 찾는데 편리함

 

문제 접근 방법

1. 이진 코드를 string 배열을 이용해 저장한 뒤, 시작점을 큐에 넣어줍니다. 이때 큐는 경로와 이진 코드를 저장합니다. 

2. 현재 이진 코드에서 전체 이진 코드와 비교합니다. 

3. 비교할 때, 차이나는 자리가 1개이며, 이전에 방문하지 않았을 경우, 해당 지점을 큐에 넣어줍니다.

4. 도착점에 도달한다면, 저장한 경로를 출력하고 return 합니다.

5. 탐색을 마쳤는데도 도착하지 못했다면, -1를 출력합니다.

 

간단한 방법임으로 코드를 보시면 이해하기 쉬울 것입니다.

// 1번째 방법

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, K;
int start, finish;
string path[1001];
int check[1001];
typedef struct qu{
	string x;
	vector<int> route;
}qu;

bool Find(string a, string b) {
	int dif = 0;
	for (int i = 0; i < K; i++) {
		if (a[i] != b[i]) dif++;
	}
	if (dif == 1) return true;
	else return false;
}

void bfs() {
	queue<qu> q;
	qu a;
	a.x = path[start];
	a.route.push_back(start);
	q.push(a);
	check[start] = 1;
	while (!q.empty()) {
		string x = q.front().x;
		vector<int> route = q.front().route;
		q.pop();
		if (x == path[finish]) {
			for (int i = 0; i < route.size(); i++) {
				cout << route[i] << " ";
			}
			return;
		}
		for (int i = 1; i <= N; i++) {
			if (Find(path[i], x) && check[i] == 0) {
				check[i] = 1;
				qu xx;
				xx.x = path[i];
				xx.route = route;
				xx.route.push_back(i);
				q.push(xx);
			}
		}
	}
	cout << "-1";
}

void solve() {
	 bfs();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> path[i];
	}
	cin >> start >> finish;
	solve();
	return 0;
}

 

두번째 방법에 대해서 설명하겠습니다.

 

이진 코드들의 입력과 동시에, 해당 코드의 1의 갯수를 확인합니다.

1의 갯수에 따라서 해당하는 vector에 저장합니다. 이때 vector는 이진 코드, 이진 코드의 번호를 저장합니다.

시작 지점에서 1의 갯수가 1개씩 차이나는 곳을 확인합니다.

이때 조건을 만족한다면, queue에 넣어줍니다.

 

문제 접근 방법

1. 이진 코드들의 1의 갯수를 기준으로 vector에 저장합니다.

2. 현재 탐색하려는 이진 코드와 1의 갯수가 1개씩 차이나는 이진 코드들만 탐색합니다.

3. 다른 곳이 1개이며, 이전에 방문하지 않았을 경우 queue에 넣어줍니다.

4. 탐색중 도착점에 도달했다면, 경로를 출력하고 return 해줍니다.

5. 탐색을 마쳤는데도 도달하지 못했다면 -1를 출력해줍니다. 

 

 

자세한 것은 코드를 참고해주세요

// 2번째 방법

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, K;
int start, finish;
string num[1001];
vector<pair<string, int>> path[31];
int check[1001];
int dx[2] = { -1,1 };

typedef struct qu {
	string x;
	int one;
	vector<int> route;
}qu;

int Find_one(string a) {
	int one = 0;
	for (int i = 0; i < K; i++) {
		if (a[i] == '1') {
			one++;
		}
	}
	return one;
}

bool Dif(string a, string b) {
	int dif = 0;
	for (int i = 0; i < K; i++) {
		if (a[i] != b[i]) dif ++;
	}
	if (dif == 1) return true;
	else return false;
}

void bfs(int start_one, string a) {
	queue<qu> q;
	qu aa;
	aa.one = start_one;
	aa.x = a;
	aa.route.push_back(start);
	q.push(aa);
	check[start] = 1;
	while (!q.empty()) {
		string x = q.front().x;
		int one = q.front().one;
		vector<int> route = q.front().route;
		q.pop();
		if (x == num[finish]) {
			for (int i = 0; i < route.size(); i++) {
				cout << route[i] << " ";
			}
			return;
		}
		for (int i = 0; i < 2; i++) {
			int one_ = one + dx[i];
			if (one_ >= 0 && one_ <= K) {
				for (int j = 0; j < path[one_].size(); j++) {
					string x1 = path[one_][j].first;
					int yy = path[one_][j].second;
					if (check[yy] == 0 && Dif(x1,x)) {
						check[yy] = 1;
						qu xx;
						xx.one = one_;
						xx.route = route;
						xx.x = x1;
						xx.route.push_back(yy);
						q.push(xx);
					}
				}
			}
		}
	}
	cout << "-1";
}

void solve() {
	int start_one = Find_one(num[start]);
	bfs(start_one, num[start]);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		string a;
		cin >> a;
		num[i] = a;
		int one = Find_one(a);
		path[one].push_back(make_pair(a, i));
	}
	cin >> start >> finish;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!