백준 2873 / C++

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

2873번: 롤러코스터

 

[ 풀이 ] 

홀수인 변이 있다면 전부 방문할 수 있음은 자명하다.

모두 짝수인 경우의 문제를 풀자. 규칙을 찾아보자. 전부 방문하는건 불가능하다. 증명은 다음과 같다. 

전부 방문하려면 (r-1)(c-1)개의 화살표가 필요하다. 이 값은 홀수이다. 

그런데 시작점에서 끝점으로 가는데엔 짝수번의 화살표가 필요하다. 따라서 홀짝성에 위배된다. 

그럼 되도록 1개만 제외하고 방문하고 싶다.  이런 문제의 아이디어는 컬러링을 생각하는게 좋다. 

체스판처럼 검은색과 흰색을 번갈아칠하자. 시작점을 검은색으로 치면, 흰색을 하나 제외할 때만 1칸만

제외하고 이동할 수 있다. 만약 검은칸을 제외하면 흰색, 검은색이 1개씩 빠져서 항상 2개가 빠지게 된다.

이 때 같은칸의 흰색 1칸만 제거하는게 항상 이득이므로 값이 제일 작은 흰색 1개만 제거하는게 최적의 해이다. 

구현은 각자 열심히 해보자. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int r, c, tx, ty, a[1001][1001];

// 시작점 왼쪽/오른쪽, i=s~e까지 두 열을 칠함
void cross(int dir, int s, int e) {
	if (s > e) return;
	// 왼쪽 위에서 시작
	if (dir == 0) {
		for (int i = s; i <= e; i++) {
			cout << (i % 2 ? "R" : "L");
			if (i != e) cout << "D";
		}
	}
	// 오른쪽 위에서 시작 
	else {
		for (int i = s; i <= e; i++) {
			cout << (i % 2 ? "L" : "R");
			if (i != e) cout << "D";
		}
	}
}

void solve(int r, int c) {
	// r이 홀수
	if (r % 2) {
		for (int i = 1; i <= r; i++) {
			for (int j = 2; j <= c; j++) {
				cout << (i % 2 ? "R" : "L");
			}
			if (i != r) cout << "D";
		}
	}
	// r이 짝수, c가 홀수
	else if (c % 2) {
		for (int j = 1; j <= c; j++) {
			for (int i = 2; i <= r; i++) {
				cout << (j % 2 ? "D" : "U");
			}
			if (j != c) cout << "R";
		}
	}
	// 둘 다 짝수
	else {
		int l = ty - !(ty % 2); // 제거할 칸과 인접한 홀수번째 열의 인덱스
		// 그 전까진 DDDD... UUUU... 반복
		for (int j = 1; j <= l - 1; j++) {
			for (int i = 2; i <= r; i++) {
				cout << (j % 2 ? "D" : "U");
			}
			if (j != l - 1) cout << "R";
		}
		// 제거할 칸이 시작점이 아니면 
		if (l >= 3) cout << "R";
		
		// 두 열을 칠한다. case 2가지  
		if (tx % 2 == 0) {
			cross(0, 1, tx - 1);
			cout << "D";
			if (tx != r) cout << "D";
			cross(1, 1, r - tx);
		}
		else {
			cross(0, 1, tx - 1);
			cout << "D";
			if (tx != 1) cout << "D";
			cross(0, 1, r - tx);
		}
		// 두열 이후 나머지 열 
		if (l + 1 != c) cout << "R";
		for (int j = l + 2; j <= c; j++) {
			for (int i = 2; i <= r; i++) {
				cout << (j % 2 ? "U" : "D");
			}
			if (j != c) cout << "R";
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> r >> c;
	int temp = 1001;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> a[i][j];
			if ((i + j) % 2 && a[i][j] < temp) {
				temp = a[i][j];
				tx = i, ty = j; // 제거할 칸 인덱스 갱신 
			}
		}
	}
	solve(r, c);
}