BOJ_5213 : 과외맨

문제

과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다.

얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다.

일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에서 스페인어를 과외 받았다.

오랜 고서에 의하면, 고대 마야인은 하늘을 날아다니는 재주가 있었다고 한다. 과외맨은 매일 밤 하늘을 바라보며 마야인들의 흔적을 찾으려고 애를 썼다.(이하생략)

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른쪽에 쓰여 있는 숫자는 Bi이다.

출력

첫째 줄에 가장 짧은 경로의 길이 (타일의 개수)를 출력한다.

둘째 줄에는 경로 상의 타일의 번호를 공백으로 구분하여 순서대로 출력한다. 만약, 가장 짧은 경로가 여러 가지라면, 아무거나 출력하면 된다.

C++ 코드

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

using namespace std;
// 홀수 줄
int dx[] = { -1, 0, 1 , -1, 0, 1 };
int dy[] = { 0, -1, 0 ,1, 1 ,1 };
// 짝수 줄
int dx1[] = { -1, 0, 1, -1, 0, 1 };
int dy1[] = { -1,-1,-1, 0,1,0 };
// 6방향 표현
int n;



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

	// 도미노 하나를 pair 로 입력받음
	cin >> n;
	vector< vector< pair<int, int> > > v(n, 
		vector< pair<int, int>>(n));
	// 거리
	vector< vector<int> > dep(n, vector<int>(n,-1));
	// 직전 도미노
	vector< vector< pair<int, int> > > from(n,
		vector< pair<int, int>>(n));

	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			for (int j = 0; j < n; j++) {
				int x, y;
				cin >> x >> y;
				v[i][j] = make_pair(x, y);	
			}
		}
		else {
			for (int j = 0; j < n - 1; j++) {
				int x, y;
				cin >> x >> y;
				v[i][j] = make_pair(x, y);
			}
		}
	}

	queue< pair<int, int> > q;
	dep[0][0] = 1;
	from[0][0] = make_pair(0, 0);
	q.push(make_pair(0, 0));

	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		// 홀수줄
		if ((x % 2) == 1) {
			for (int k = 0; k < 3; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (nx < 0 || nx >= n || ny < 0) continue;
				if ((nx % 2) == 0 && ny >= n) continue;
				if ((nx % 2) == 1 && ny >= n - 1) continue;
				if (dep[nx][ny] != -1) continue;

				if (v[x][y].first == v[nx][ny].second) {
					q.push(make_pair(nx, ny));
					dep[nx][ny] = dep[x][y] + 1;
					from[nx][ny] = make_pair(x, y);
				}
			}
			for (int k = 3; k < 6; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (nx < 0 || nx >= n || ny < 0) continue;
				if ((nx % 2) == 0 && ny >= n) continue;
				if ((nx % 2) == 1 && ny >= n - 1) continue;
				if (dep[nx][ny] != -1) continue;

				if (v[x][y].second == v[nx][ny].first) {
					q.push(make_pair(nx, ny));
					dep[nx][ny] = dep[x][y] + 1;
					from[nx][ny] = make_pair(x, y);
				}
			}
		}
		else {
			// 짝수줄
			for (int k = 0; k < 3; k++) {
				int nx = x + dx1[k];
				int ny = y + dy1[k];
				if (nx < 0 || nx >= n || ny < 0) continue;
				if ((nx % 2) == 0 && ny >= n) continue;
				if ((nx % 2) == 1 && ny >= n - 1) continue;
				if (dep[nx][ny] != -1) continue;

				if (v[x][y].first == v[nx][ny].second) {
					q.push(make_pair(nx, ny));
					dep[nx][ny] = dep[x][y] + 1;
					from[nx][ny] = make_pair(x, y);
				}
			}
			for (int k = 3; k < 6; k++) {
				int nx = x + dx1[k];
				int ny = y + dy1[k];
				if (nx < 0 || nx >= n || ny < 0) continue;
				if ((nx % 2) == 0 && ny >= n) continue;
				if ((nx % 2) == 1 && ny >= n - 1) continue;
				if (dep[nx][ny] != -1) continue;

				if (v[x][y].second == v[nx][ny].first) {
					q.push(make_pair(nx, ny));
					dep[nx][ny] = dep[x][y] + 1;
					from[nx][ny] = make_pair(x, y);
				}
			}

		}
	}
	int x = n - 1;
	int y = n - 1;
	// 과제 못찾으면 가장 큰 도미노
	while (dep[x][y] == -1) {
		y -= 1;
		if (y < 0) {
			x -= 1;
			y = n - 1;
			if (x % 2 == 1) {
				y -= 1;
			}
		}
	}
	cout << dep[x][y] << '\n';

	// 경로 출력
	deque<int> dq;
	for(int i=0; i< n*n; i++){
		if (x == 0 && y == 0) break;
		
		dq.push_front((x * n)
			- (x / 2) + y + 1);

		int temp = from[x][y].first;
		y = from[x][y].second;
		x = temp;
	}
	dq.push_front((x* n) - (x / 2) + y + 1);
	int s = dq.size();

	for (int i = 0; i < s; i++) {
		cout << dq.front() << ' ';
		dq.pop_front();
	}
	cout << '\n';

	return 0;
}