[C++] 백준/BOJ - 22868 : 산책(small)

문제 이해 단계

 

2차원 격자가 주어지고, 각 정점의 연결 정보들이 주어진다.

시작 위치 S와 도착 위치가 E가 주어졌을 때 
S에서 E로 가는 최단 거리를 구하고,

그 후 S에서 E로 갔을 때, 방문하지 않았던 정점만을 사용하여
다시 E에서 S로 최단거리로 돌아간다.

이때의 최단 거리의 합을 구하는 문제이다.

 

---

문제 접근 단계

해당 문제를 어떻게 푸는지에 대한 키워드는

1.  최단 경로의 거리를 구한다는 것
2. 산책을 할 수 있는 경로의 데이터만 주어진 다는 것이다.

1번의 키워드에서 경로를 탐색하여 최소 횟수를 찾는
DFS나 BFS를 사용해야 한다는 것을 알았다.

DFS와 BFS 중 어떤 것으로 풀어야 효율적 일지 고민 중이었는데
2번 키워드에서 힌트를 얻었다.

산책을 할 수 있는 경로만 주어진다는 것은
어떤 경우에도 도착했다가 돌아올 수 있다는 것이다.

이를 여태껏 풀어왔던, 2차원 바둑판에 있는 최단 경로 문제라고 대입해 보면,

바둑판 배열이 노드로 바뀌었을 뿐,
동일한 메커니즘으로 작동하는 것을 볼 수 있다.

그래서 나는 BFS로 이 문제를 풀면 된다고 생각했다.

이 문제는 최단 경로로 도착지로 갔다가,
방문하지 않은 정점으로 시작점까지 돌아와야 한다.

최단 경로로 도착지까지 갔다가
방문한 곳을 제외하고 최단 경로로 복귀하려면,
방문한 정점은 제외하고 한번 더 BFS를 돌려야 한다.

즉, S에서 E까지의 최단거리를 갈 때의 지나는 정점을 알고 있어야 한다.

이를 알기 위해서 visit배열을 벡터 배열로 받아, 이전에 방문했던 정보를 차례대로 넘겼다.
이렇게 하면 최종적으로 도착지에는 최단경로로 왔을 때의 정점의 번호들이 담겨있다.

이제 그 번호들에 해당하는 정점을 모두 제외하고
E에서 S로 가는 최단 경로를 구한다.

핵심은 S에서 E로가는 최단경로를 구할 때, 정점의 정보들을 저장해 둔다는 것이다.

말로는 이해가 어려울 수도 있으니 코드를 통해 설명하겠다.

 

---

문제 구현 단계

vector<int> map[10001];
pair<bool, vector<int>> c[10001];
int S, E;
vector<int> answer;

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		map[v1].push_back(v2);
		map[v2].push_back(v1);
	}
	cin >> S >> E;
	int go, back;
	Bfs(S, E);
	go = c[E].second.size() - 1;
	vector<int> visited = c[E].second;

방문을 확인할 c배열을 pair <bool, vector <int>>로 선언했다.

첫 번째에서 방문을 확인하고, 두 번째에 방문했던 정점의 번호를 저장한다.

입력값을 map 리스트에 노드에 연결하고 S와 E 정보를 저장한다.
그리고 BFS함수를 실행한다. BFS함수에 대해서는 밑에서 서술하겠다.

계산된 c [E]. second에서 방문한 정점들의 정보를 받아온다.
받아온 노드의 번호를 visit이라는 새로운 배열에 저장해 둔다.

그리고 계산된 최단 경로를 go에 저장한다.
1을 빼주는 이유는 여기에 자기 자신도 들어가 있기 때문이다.

void Bfs(int s, int e) {
	queue<int> q;
	q.push(s);
	c[s].first = true;
	while (!q.empty()) {
		int x = q.front();
		c[x].second.push_back(x);
		if (x == e) return;
		q.pop();
		sort(map[x].begin(), map[x].end());
		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (!c[nx].first) {
				c[nx].first = true;
				c[nx].second = c[x].second;
				q.push(nx);
			}
		}
	}
}

BFS는 일반적인 방식과 같다.

첫 번째 매개변수는 시작 노드,
두 번째로는 도착 노드를 받는다.

방문 정보를 true로 바꿔주면서
큐와 리스트에 계속 넣어주는 것을 반복한다.

그리고 해당 큐에 있던 노드가
도착노드와 같은 return 하고 종료한다.

그리고 중간에 연결된 노드들을 오름차순 정렬하는데,
그 이유는 문제에서 두 개의 경로 중 사전순으로 빠른 것이 우선순위라고 했기 때문이다.

이 과정을 제외하면 일반적인 BFS와 같다.

	for (int i = 1; i < 10001; i++) {
		c[i].first = false;
		c[i].second.clear();
	}

	for (int i = 0; i < visited.size(); i++) {
		int x = visited[i];
		c[x].first = true;
	}
	c[S].first = false;
	c[E].first = false;
	Bfs(E, S);
	back = c[S].second.size() - 1;
	cout << go + back;

BFS를 한번 더 돌려주기 위해 방문 정보를 모두 초기화한다.

이후 이미 방문했던 노드들을 방문처리하기 위해
visited에 저장해 놨던 노드들을 모두 방문처리한다.

밑에 S와 E를 한번 더 false로 해주는 이유는
S에서 바로 E로 가는 경우에는 위에서 이미 방문된 거로 처리되기 때문이다.

이후 BFS를 돌려 같은 방식으로
back을 구한 후 go와 back을 더해 답을 구한다.

밑에는 전체 코드를 올리고 풀이를 끝내겠다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> map[10001];
pair<bool, vector<int>> c[10001];
int S, E;
vector<int> answer;
void Bfs(int s, int e) {
	queue<int> q;
	q.push(s);
	c[s].first = true;
	while (!q.empty()) {
		int x = q.front();
		c[x].second.push_back(x);
		if (x == e) return;
		q.pop();
		sort(map[x].begin(), map[x].end());
		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (!c[nx].first) {
				c[nx].first = true;
				c[nx].second = c[x].second;
				q.push(nx);
			}
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		map[v1].push_back(v2);
		map[v2].push_back(v1);
	}
	cin >> S >> E;
	int go, back;
	Bfs(S, E);
	go = c[E].second.size() - 1;
	vector<int> visited = c[E].second;

	for (int i = 1; i < 10001; i++) {
		c[i].first = false;
		c[i].second.clear();
	}

	for (int i = 0; i < visited.size(); i++) {
		int x = visited[i];
		c[x].first = true;
	}
	c[S].first = false;
	c[E].first = false;
	Bfs(E, S);
	back = c[S].second.size() - 1;
	cout << go + back;
}

 

---

시행착오

처음에는 도착할 수 있는 경로만 주어진다는 힌트를 파악하지 못해 DFS로 풀었다.
DFS로 풀다 보니 오히려 꼬이고 자꾸만 틀렸습니다가 떴다.

예외케이스가 자꾸만 생기고,
재귀함수를 자꾸만 고치다 보니 머리가 너무 복잡해지더라

그래서 문제 밑에 있는 문제 분류를 보니까
너비 우선 탐색이라고 딱 적혀 있어서 멘붕이 왔다.

곰곰이 생각해 보니까 너비 우선 탐색이 맞아서 허무했다.

너비 우선 탐색이란 걸 깨닫자마자 방식은 바로 떠올랐다.
힌트를 좀 더 곱씹는 습관을 가져야겠다.