백준 2536번 버스 갈아타기 C++ BFS

리뷰

BFS로 문제를 풀었다. 굉장히 까다로웠던 문제

 

문제 풀이

1. 구조체 배열 busInfo를 k + 1개로 초기화 해준 후 각 버스 번호의 index에 버스 구조체를 넣어준다.
2. 이때 항상 x2가 x1보다 크고 y2가 y1보다 크다는 보장이 없기 때문에 큰 값을 x2, y2로 변환하여 넣어준다.
3. 버스 노선은 직선형 이기 때문에 x가 서로 같거나 y가 서로 같을 경우도 체크해 준 후 type 변수로 넣어준다.
4. 2차 배열 buslist를 k + 2 크기로 초기화 해준다, 각 버스 노선이 인접한 경우 쌍방향으로 index를 추가해 인접 리스트를 만들어 준다.
5. 시작점과 도착점 정보를 받아준 후 각각을 인접 리스트의 0번 index, k + 1번 index로 인접 리스트를 확장해 준다.
6. 0번 index부터 bfs를 시작해 준다. k + 1에 도달했을 경우 time을 리턴 후 출력해 주면 된다.

 

참고 사항

타입에 따른 판별이 굉장히 중요한 것 같다. type변수를 통해 서로 평행한지 여부를 체크해 주는걸 추천하고, 인접 여부를 체크하기 보단 인접하지 않은 경우 continue 처리해 주는 것이 코드 작성할 때 더 편했다.

BFS의 판별 조건보단 인접 리스트를 만드는 것에 시간이 많이 소요되는 문제

 

정답 코드

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


using namespace std;

int m, n, k, b, bx1, by1, bx2, by2, sx, sy, dx, dy;

struct Bus {
	int x1, x2, y1, y2, type;
};

int bfs(int start, vector<vector<int>>& buslist) {
	queue<pair<int, int>> q;
	vector<int> v(k + 2, 0);
	q.push({ start, 0 });
	v[start] = 1;

	while (!q.empty()) {
		int cn = q.front().first; int time = q.front().second;
		q.pop();
		for (int i : buslist[cn]) {
			if (v[i]) continue;
			if (i == k + 1) return time;
			v[i] = 1;
			q.push({ i, time + 1 });
		}
	}
}

int main() {
	cin >> m >> n >> k;
	vector<Bus> busInfo(k + 1);
	for (int i = 0; i < k; i++) {
		cin >> b >> bx1 >> by1 >> bx2 >> by2;
		if (bx1 > bx2) swap(bx1, bx2);
		if (by1 > by2) swap(by1, by2);
		int type;
		if (bx1 == bx2) type = 2;
		if (by1 == by2) type = 1;
		busInfo[b] = { bx1, bx2, by1, by2, type };
	}
	vector<vector<int>> buslist(k + 2);
	for (int i = 1; i <= k; i++) {
		Bus& b1 = busInfo[i];
		for (int j = i + 1; j <= k; j++) {
			Bus& b2 = busInfo[j];
			if (b1.type == 2 && b2.type == 2) {
				if (b1.x1 != b2.x2) continue;
				if (b1.y2 - b2.y2 >= 0 && b1.y1 > b2.y2) continue;
				if (b2.y2 - b1.y2 >= 0 && b2.y1 > b1.y2) continue;
			}
			else if (b1.type == 1 && b2.type == 1) {
				if (b1.y1 != b2.y2) continue;
				if (b1.x2 - b2.x2 >= 0 && b1.x1 > b2.x2) continue;
				if (b2.x2 - b1.x2 >= 0 && b2.x1 > b1.x2) continue;
			}
			else {
				if (b1.type == 2 && b2.type == 1) {
					if (b2.x1 > b1.x1 || b1.x1 > b2.x2) continue;
					if (b1.y1 > b2.y1 || b2.y1 > b1.y2) continue;
				}
				if (b1.type == 1 && b2.type == 2) {
					if (b1.x1 > b2.x1 || b2.x1 > b1.x2) continue;
					if (b2.y1 > b1.y1 || b1.y1 > b2.y2) continue;
				}
			}
			buslist[i].push_back(j);
			buslist[j].push_back(i);
		}
	}
	cin >> sx >> sy >> dx >> dy;
	Bus sb = { sx, sy, sx, sy };
	Bus db = { dx, dy, dx, dy };
	for (int i = 1; i <= k; i++) {
		Bus& bus = busInfo[i];
		if (bus.x1 <= sx && sx <= bus.x2 && bus.y1 <= sy && sy <= bus.y2) {
			buslist[i].push_back(0);
			buslist[0].push_back(i);
		}
		if (bus.x1 <= dx && dx <= bus.x2 && bus.y1 <= dy && dy <= bus.y2) {
			buslist[i].push_back(k + 1);
			buslist[k + 1].push_back(i);
		}
	}
	cout << bfs(0, buslist);
}