백준 5214번 환승 C++ BFS

리뷰

인접 리스트와 방문 배열 2개를 활용하여 해결한 문제

 

문제 풀이

1. 노드 배열을 n + 1 크기로, 하이퍼 튜브 배열을 m + 1배열로 초기화 해준다.
2. m * k 크기의 for문을 개행하고, 입력값을 받을 때 하이퍼 튜브와 노드의 인접 리스트에 쌍방향으로 push 해준다.
3. 큐에는 도시(노드) 정보와 이동 횟수, 현재가 노드인지 하이퍼 튜브인지를 구별할 변수를 구조체로 넣어준다.
4. BFS를 실행하고 현재가 하이퍼 튜브일 경우 방문 처리 및 튜브 안의 노드 인자를 큐에 추가해 준다. 이때 이동 횟수를 증가 시키고 노드 정보라는 표시를 해 준다.
5. 현재가 노드일 경우 방문 처리 및 연결된 하이퍼 튜브를 큐에 추가해 준다. 이번엔 이동 횟수를 증가 시키지 않는다. 마찬가지로 하이퍼 튜브라는 표시를 해 준다.
6. 큐에서 pop한 현재 노드가 목표 노드에 위치했고, 하이퍼 튜브가 아니라면 이동 횟수를 반환 후 출력해 주면 된다.
7. 만약 while루프가 끝날 때 까지 목표 노드에 도착하지 못했다면 -1을 출력해 준다.

 

참고 사항

BFS내에서 하이퍼 튜브와 노드를 구분지어 처리해 주어야 하는 것과 빠져나오는 조건에서 현재 노드가 하이퍼 튜브인지 아닌지 여부를 파악하는 정도? 를 잘 생각하면 될 것 같다.

 

 

정답 코드

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

using namespace std;

int n, k, m;
vector<int> ans;

struct pos {
	int city, cnt, isnode;
};

int bfs(vector<vector<int>>& nodes, vector<int>& nv, vector<vector<int>>& hyper, vector<int>& hv) {
	queue<pos> q;
	q.push({ 1, 1, 0 });
	//nv[1] = 1;
	
	while (!q.empty()) {
		pos cur = q.front();
		q.pop();
		int cn = cur.city, cnt = cur.cnt, h = cur.isnode;
		if (cn == n && h == 0) return cnt;
		if (h && !hv[cn]) {
			hv[cn] = 1;
			for (int hype : hyper[cn]) {
				if (nv[hype]) continue;
				q.push({ hype, cnt + 1, 0 });
			}
			continue;
		}
		if (!h && !nv[cn]) {
			nv[cn] = 1;
			for (int node : nodes[cn]) {
				if (hv[node]) continue;
				q.push({ node, cnt, 1 });
			}
			continue;
		}
	}
	return -1;
}

int main() {
	cin >> n >> k >> m;
	vector<vector<int>> nodes(n + 1);
	vector<vector<int>> hyper(m + 1);
	vector<int> nv(n + 1, 0);
	vector<int> hv(m + 1, 0);
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < k; j++) {
			int a;
			cin >> a;
			hyper[i].push_back(a);
			nodes[a].push_back(i);
		}
	}
	cout << bfs(nodes, nv, hyper, hv);
}