알고리즘(C++) / 백준 2873 : 롤러코스터

2873

www.acmicpc.net/problem/2873

2873번: 롤러코스터

 

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

 

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

 

코드

//2873 - 롤러코스터
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
	int R, C;

	cin >> R >> C;

	int **pleasure = new int*[R];
	//2차원 배열 동적할당
	for (int i = 0; i < R; i++) {
		pleasure[i] = new int[C];
	}

	pair <int, int> blank;
	int min = 1001; //1000최대
	//배열 입력
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> pleasure[i][j];
			if (min > pleasure[i][j] && (i + j) % 2 == 1) {
				min = pleasure[i][j];
				blank.first = i;
				blank.second = j;
			}
		}
	}


	string move;
	int i, j;
	if (R % 2 == 1) { //R이 홀수 일때
		for (i = 0; i < R; i++) {
			for (j = 0; j < C - 1; j++) {
				if (i % 2 == 0)
					move += 'R'; //오른쪽 방향
				else
					move += 'L'; //왼쪽 방향
			}
			if (i == R - 1)
				break;
			move += 'D'; //아래쪽 방향
		}
	}
	else if (C % 2 == 1) { //C가 홀수 일때
		for (i = 0; i < C; i++) {
			for (j = 0; j < R - 1; j++) {
				if (i % 2 == 0)
					move += 'D'; //아래쪽 방향
				else
					move += 'U'; //위쪽 방향
			}
			if (i == C - 1)
				break;
			move += 'R'; //오른쪽 방향
		}
	}
	else { //R, C 모두 짝수 일때
		//모두 짝수일 때는 모든 칸을 지나갈수 없음. 무조건 한칸은 지나가지 않음
		int r, c;
		if (blank.first % 2 == 1)
			r = blank.first - 1; //blank가 있는 윗줄까지
		else
			r = blank.first; //blank가 있는 줄까지 

		//blank가 있는 줄 전까지  
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < C - 1; j++) {
				if (i % 2 == 0)
					move += 'R';
				else
					move += 'L';
			}
			move += 'D';
		}


		//blank 전
		c = blank.second;

		for (int i = 0; i < c; i++) {
			if (i % 2 == 0)
				move += "DR";
			else
				move += "UR";
		}

		//blank 후
		for (int i = c; i < C - 1; i++) {
			if (i % 2 == 0)
				move += "RD";
			else
				move += "RU";
		}

		for (int i = r + 2; i < R; i++) {
			move += 'D';
			for (int j = 0; j < C - 1; j++) {
				if (i % 2 == 0)
					move += 'L';
				else
					move += 'R';
			}
		}

	}

	cout << move << endl;

	return 0;
}

 

설명

이번 문제는 세가지 경우로 나눠서 풀 수 있다.

1. R이 홀수일 때
2. C가 홀수일 때
3. R과 C 모두 짝수일 때

• R이 홀수일 때

→	→	→	↓
↓	←	←	←
→	→	→	☆

R이 홀수일 때는 다음과 같이 움직일 수 있다.

롤러코스터의 위치가 짝수번째이면 오른쪽으로 이동(배열은 0부터 시작), 홀수번째이면 왼쪽으로 이동한다. 이때 끝에 닿으면 아래쪽으로 이동힌다. 

 

• C가 홀수일 때

↓	→	↓
↓	↑	↓
↓	↑	↓
→	↑	☆

C가 홀수일 때는 다음과 같이 움직일 수 있다.

롤러코스터의 위치가 짝수번째이면 오른쪽으로 이동(배열은 0부터 시작), 홀수번째이면 왼쪽으로 이동한다. 이때 끝에 닿으면 아래쪽으로 이동힌다. 

 

• R과 C 모두 짝수일 때

R과 C가 모두 짝수일 때는 모든 칸을 지나치지 못한다. 최소 한칸은 지나치지 못한다. 기쁨의 합이 최대로 하기 위해서는 지 제일 작은 기쁨인 한 칸을 제외하고 모든 칸을 지나쳐야한다.

o	x	o	x
x	o	x	o
o	x	o	x
x	o	x	o

o로 표시된 칸은 무조건 지나쳐야하고 x로 표시된 칸 중 제일 가장 작은 기쁨인 한 칸을 빼고 지나칠 수 있다. 

x칸 중에서 제일 작은 기쁨을 찾아 blank에 좌표를 저장해둔다. 

X가 blank라 한다.

 

2줄씩 쌍을 지어서 이동할 수있다.

위 두줄에 blank가 없다면 오른쪽으로 이동, 끝까지 도달했더면 아래쪽으로 한 칸 이동, 그 후 왼쪽으로 이동한다.

그 다음 두줄에 blank가 있을때까지 반복하고

 

다음 두줄에 blank가 있다면  blank에 닿을때까지 DR과 UR을 반복한다. blank에 닿은 후에는 RD과 RU을 행의 끝까지 반복한다. 

 

blank가 지난 후 다음 두줄은 왼쪽으로 이동, 끝까지 도달했더면 아래쪽으로 한 칸 이동, 그 후 오른쪽으로 이동한다. 마지막 위치까지 반복한다. 

 

다음과 같이 롤러코스터의 경로를 출력할 수 있다.

 

 

출력

 

고찰

row와 column 둘 중 하나가 홀수일 때는 쉽게 풀 수 있었다. 

하지만 row와 column이 모두 짝수일 때는 행렬 중 한 칸은 가지 못해서 어떻게 가야하는지 생각하지 못했다. 

알고리즘 문제는 두시간 안에 풀지 못하면 고민하기 보다는 해결책을 찾아보는 것이 낫다. 그래서 구글링해서 문제를 풀 수 있었다.

 

 

난이도

●●●◐○

오래 생각했다면 풀 수도 있었을거 같은데, 알고리즘은 빠른시간내에 푸는 것이 중요하다.

짧은 시간내에 해법을 찾기에는 어려웠다.