[BOJ 5213 // C++] 과외맨

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5213번 문제인 과외맨이다.
문제는 아래 링크를 확인하자.

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

5213번: 과외맨

문제의 상황은 주어지는 각 도미노 타일을 노드로, 서로 인접한 변을 통해 이동할 수 있는 관계에 있는 도미노쌍을 에지로 생각해 그래프로 모델링할 수 있다. 이 그래프의 첫 칸에서 BFS를 이용하면 각 도미노타일로 가기 위해 거쳐가야 하는 도미노의 개수의 최솟값을 구해낼 수 있다.

 

주어진 배열의 각 칸이 몇번 도미노의 위인지를 기록하는 배열을 따로 하나 만들어 문제를 편하게 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;

int id = 1;
int tileid[1000][1000];
int arr[1000][1000];

vector<int> G[250001];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int backtrack[250001];

void init() {
	cin >> N;
	for (int r = 0; r < N; r++) {
		if (r & 1) {
			for (int c = 1; c < 2 * N - 1; c += 2) {
				tileid[r][c] = tileid[r][c + 1] = id++;
				cin >> arr[r][c] >> arr[r][c + 1];
			}
		}
		else {
			for (int c = 0; c < 2 * N; c += 2) {
				tileid[r][c] = tileid[r][c + 1] = id++;
				cin >> arr[r][c] >> arr[r][c + 1];
			}
		}
	}

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < 2 * N; c++) {
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= N || cc < 0 || cc >= 2 * N || tileid[r][c] == tileid[rr][cc] || arr[r][c]!=arr[rr][cc]) continue;
				G[tileid[r][c]].emplace_back(tileid[rr][cc]);
				G[tileid[rr][cc]].emplace_back(tileid[r][c]);
			}
		}
	}
}

void bfs() {
	queue<int> que;
	backtrack[1] = -1; que.push(1);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G[cur]) {
			if (backtrack[nxt]) continue;
			backtrack[nxt] = cur;
			que.push(nxt);
		}
	}
}

vector<int> ans;

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

	init();
	bfs();
	
	while (backtrack[id] == 0) id--;
	while (id > 0) {
		ans.emplace_back(id);
		id = backtrack[id];
	}

	cout << ans.size() << '\n';
	while (!ans.empty()) {
		cout << ans.back() << ' ';
		ans.pop_back();
	}
}