[Codeforces] CodeCraft-20 - D. Nash Matrix

문제 링크

문제 해석

간단히 요약하자면 보드게임의 결과가 주어졌을 때, 이 결과가 나오는 보드판을 만들 수 있으면 출력하고, 없으면 불가능하다고 출력하는 문제다.
Nash가 만든 보드게임은 NxN크기의 보드판에서 진행된다. 여기에는 다섯개의 경우가 있는데, 상, 하, 좌, 우로 한 칸씩 움직이는 각각의 명령과 마지막으로 해당 자리에서 벗어날 수 없는 ‘X’표시이다.
엘리스가 각각의 칸에서 시작했을 때 종료되는 칸이 어디인지 표시한 정보를 주었을 때, 그 결과가 나오는 보드판을 출력해야한다.

풀이

간단히 정리하자.

1. 무한루프를 도는 칸은 2개 이상이 연결되어있을 경우 반드시 무한루프가 가능하다.(VALID하다.)
2. 반대로 무한루프를 도는 칸이 1개만 따로 떨어져 존재할 경우 무한루프가 불가능하다.(INVALID하다.)
3. 어떠한 ‘x’로 향하는 칸들은 서로 다른 ‘x’로 향하는 경로상에서 마주칠 수 없다.(마주칠 경우 향하는 ‘x’가 반드시 같아지기 때문에 도착지가 다르다는 것에 모순된다.)
4. 따라서 그냥 ‘x’(출발지와 도착지가 같은 경우)에서 시작하여 나로 도달하는 경로를 따라 쭉 탐색해주면 된다.

요런 의식의 흐름을 통해 구현하면 된당.

소스코드

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <string.h>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef pair<int, int> PII;
 
queue<PII> q;
PII mp[1005][1005];
char state[1005][1005], str[4] = { 'L', 'R', 'D', 'U' }, str2[4] = { 'R', 'L', 'U', 'D' };
int dr[4] = { 0, 0,-1,1 }, dc[4] = { 1,-1,0,0 }, n;
 
bool is_in_range(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n;
}
 
int main(void) {
	int a, b;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d %d", &a, &b);
			a--; b--;
			mp[i][j] = { a, b };
			if (i == a && j == b) {
				q.push({ a, b });
				state[a][b] = 'X';
			}
		}
	}
	while (!q.empty()) {
		int xx = q.front().first, yy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = xx + dr[i], y = yy + dc[i];
			if (is_in_range(x, y) && !state[x][y] && mp[xx][yy] == mp[x][y]) {
				state[x][y] = str[i];
				q.push({ x, y });
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (mp[i][j] == PII{-2, -2}) {
				q.push({ i, j });
				for (int k = 0; k < 4; k++) {
					int x = i + dr[k], y = j + dc[k];
					if (is_in_range(x, y) && !state[x][y] && mp[x][y] == PII{ -2,-2 }) {
						state[i][j] = str2[k];
					}
				}
				while (!q.empty()) {
					int xx = q.front().first, yy = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++) {
						int x = xx + dr[k], y = yy + dc[k];	
						if (is_in_range(x, y) && !state[x][y] && mp[x][y] == PII{ -2,-2 }) {
							state[x][y] = str[k];
							q.push({ x, y });
						}
					}
				}
			}
			if (!state[i][j]) {
				printf("INVALID\n");
				return 0;
			}
		}
	}
	printf("VALID\n");
	for (int i = 0; i < n; i++) {
		printf("%s\n", state[i]);
	}
}