[백준문제풀이] 2873 롤러코스터

 

풀이일시 : 2020-12-20

​

 

문제 :

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

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

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

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

​

​

입력 :

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

ex)

3 3

5 1 3

2 4 8

1 1 2

​

​

출력 :

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

ex)

RRDLLDRR

​

​

풀이 :

​

왼쪽 위에서 오른쪽 아래로 도달해야하는데 그 경로가 최대한 많은 숫자를 지나야 한다.

​

가로는 홀수와 짝수의 경우가 있고 세로도 마찬가지 이므로 총 네가지의 경우가 있을것이다.

​

1) 세로 홀수 가로 홀수

시작 →	→	↓
↓	←	←
→	→	끝 →

2) 세로 홀수 가로 짝수

시작 →	→	→	↓
↓	←	←	←
→	→	→	끝 →

3) 세로 짝수 가로 홀수

시작 ↓	→	↓
↓	↑	↓
↓	↑	↓
→	↑	끝 ↓

​

4) 세로짝수 가로 짝수

시작 →	→	→	→	→	↓
↓	←	←	←	←	←
↓	​	→	↓	→	↓
→	→	↑	→	↑	↓
↓	←	←	←	←	←
→	→	→	→	→	끝 →

이런식으로 탐색할 수 있을것이다.

탐색방법은 1)과 2) 가 같고 3), 4) 까지 총 세 가지로 나뉘게 된다. 이의 알고리즘을 작성해주면 될것이다.

​

탐색방법 1,2,3 은 모두 탐색할 수 있으나 4는 가장 작은 칸 하나를 남겨둬야한다.

​

​

탐색방법4) 에 대해 더 생각해보자

​

방법4는 1,2,3과 다르게 한칸이 무조건 비게 되는데 어떻게 최소값을 알 수 있고 그 칸에는 조건이 있을까?

 

위의 표에서 빨간색 부분이 지워도 되는 부분이다. 흰색 부분만 지워서는 끝점에 도달하기 위한 경로가 나오지 않게된다. 빨간색중에 최소인 점을 하나 제외하고 경로를 짜는 것이 최대의 행복을 얻을 수 있다.

​

그러면 동작을 분할해보자.

​

동작1) 지나치지 말아야 할 좌표가 주황색일때, 초록색일때 첫번째 동작이다. 주확색은 자신의 행의 -1 초록색은 자신의 행의 -2 지점에서 멈춰둔다.

 

동작2) 두번째 구분동작이다. 각 좌표 전까지 DR - UR 동작을 반복해준다. 주황색이라면 DR 한번밖에 필요하지 않을것이고 초록색 좌표라면 DR 후 UR 까지 해야 자신의 좌표까지 도달할 수 있을것이다.

​

동작3) 3번째 구분동작이다. 이 복잡한 상황을 헤쳐나가고 정상 동작을 하기위해 탈출을 도전한다.

​

 

동작4) 드디어 마지막 구분동작이다. 처음과같은 매커니즘으로 끝으로 이동하면 될것이다. (다만 처음에 D를 추가하며 시작해야 될것이다.)

 

코드로 그대로 옮겨보자

#include <iostream>
#include <algorithm>
#include <string>

#define MAX 1000
#define INF 1000000000 //10억으로 최대값을 표현
using namespace std;

int graph[MAX][MAX];
string result;

int main() {
	int R, C;
	cin >> R >> C;
	pair<int, int> no;// 지나지 말아야 할 지점. 가장 행복지수 낮은지점
	int minscore = INF;

	for (int y = 0; y < R; y++) {
		for (int x = 0; x < C; x++) {
			cin >> graph[y][x];
			//거치지 않아도 될 칸 중에 최소점수라면
			if ((y + x) % 2 && minscore > graph[y][x])
			{
				minscore = graph[y][x]; //minxcore를 갱신해주고 (계속찾기위해)
				no = { y,x }; //거치지 말아야 할 점을 저장해준다.
			}
		}
	}
	//그래프생성완료 no 까지 만들었으니 방법4)에서 그걸 피해서 움직여보자.

	if (R % 2){ //세로가 홀수 즉 탐색방법 1,2의 경우이다.
		for (int y = 0; y < R; y++){ //세로
			for (int x = 0; x < C - 1; x++) 
				if (y % 2 == 0) //짝수번 라인이면
					result += 'R'; //R
				else //홀수번 라인이면 
					result += 'L'; //L
			if (y != R - 1) //끝이라면 Down을 해야할것
				result += 'D';
		}
	}

	else if (!(R % 2) && C % 2){ 	//세로가 짝수 가로가 홀수
		for (int x = 0; x < C; x++){ //가로
			for (int y = 0; y < R - 1; y++)
				if (x % 2 == 0)
					result += 'D';
				else
					result += 'U';
			if (x != C - 1)
				result += 'R'; //끝이라면 오른쪽으로 이동
		}
	}

	else if (!(R % 2) && !(C % 2)) {
		//우선 no 좌표 전까지 위에서 아래로 내려오는 코드이다.
		int nR, nC;
		if (no.first % 2 == 1) //홀수번째 라인이면
			nR = no.first - 1; //그 전줄까지만 내려오도록한다.
		else
			nR = no.first;
		for (int y = 0; y < nR; y++) {
			for (int x = 0; x < C - 1; x++) {
				if (y % 2 == 0)
					result += 'R';
				else
					result += 'L';
			}
			result += 'D';
		}
		//그 다음 움직임은 no 좌표의 대각선 아래까지 움직이는거다.
		nC = no.second; //x좌표
		for (int x = 0; x < nC; x++) {
			if (x % 2 == 0)
				result += "DR";
			else
				result += "UR";
		}
		//no좌표를 넘어갔으면 최 우측으로 이동시켜줄것이다.
		for (int x = nC; x < C - 1; x++) {
			if (x % 2 == 0)
				result += "RD";
			else
				result += "RU";
		}

		//마지막 구분동작
		if (no.first % 2 == 0)
			nR = R - (no.first + 2);
		else
			nR = R - (no.first + 1);

		for (int y = 0; y < nR; y++) {
			result += 'D';
			for (int x = 0; x < C - 1; x++) {
				if (y % 2 == 0)
					result += 'L';
				else
					result += 'R';

			}
		}
	}
	cout << result << '\n';
	return 0;
}
​