[ boj : 22868 ] 산책(small)

https://www.acmicpc.net/problem/22868

22868번: 산책 (small)

해설 : 사전순으로 s->e 까지 도달해야 된다는게 은근히 까다롭더라구요.

전 그래서 에초에 인접리스트들을 전부 sort 해주었습니다. 

1 3

1 2

2 3

2 4

3 4

입력이 1 2 가 아닌 1 3 이 먼저 들어가게 된다면 인접리스트에는 1 3 이 더 앞서서 저장이 되겠죠??그러면 사전순으로 도달해야 됨에 있어서 너무 까다로워집니다. 

이를 해결하기 위해서 1 2 가 되도록 오름차순으로 정렬을 해주었습니다. 그러면 그냥 순차적으로 인접리스트에서 뽑는다면 그게 곧 사전순으로 접근하게 되는 것 이겠죠

그리고 방문했던 자취들을 저장해서 하나씩 뽑아오면서 다시 방문 흔적들을 남기고 난 후에 e->s 로 가는 처리를 해주면 됩니다.

다익스트라로도 해결이 가능할 것 같은 문제인데 한번 더 고심해 봐야겠어요.

#include<bits/stdc++.h>

using namespace std;

const int SIZE = (int)1e4 + 1;
int n, m;
int visit[SIZE];
vector<int> v[SIZE];

void solve();
int bfs(int x, int y, int flag);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	cin >> n >> m;
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)sort(v[i].begin(), v[i].end());
	int a, b;
	cin >> a >> b;
	cout << bfs(a, b, 0) + bfs(b, a, 1);
}
int bfs(int x, int y, int flag)
{
	queue<pair<int, vector<string>>> q;
	vector<string> vt;
	
	q.push({ x,vt });
	visit[x] = 1;

	int cnt = 0;
	vector<pair<string,vector<string>>> ans;
	while (!q.empty())
	{
		bool tflag = false;
		for (int i = q.size(); i > 0; i--) {
			pair<int, vector<string>> cur = q.front();
			q.pop();

			if (cur.first == y) {
				string str = "";
				ans.push_back({ str ,cur.second});
				tflag = true;
				break;
			}

			for (int u : v[cur.first]) {
				if (!visit[u]) {
					vector<string> tmp = cur.second;
					tmp.push_back(to_string(u));
					q.push({ u, tmp });
					if(u!=y)
						visit[u] = 1;
				}
			}
		}
		if (tflag)break;
		cnt++;
	}
	if (!flag) {
		for (int i = 1; i <= n; i++)visit[i] = 0;
		for (string u : ans[0].second) {
			visit[stoi(u)] = 1;
		}
	}
	return cnt;
}