[BOJ]2873번: 롤러코스터 (c++)

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

2873번: 롤러코스터

 

그리디

#include <iostream>
#include <vector>

using namespace std;

struct pos {
	int x, y;
};

void print_path(vector<vector<int>> &board, const pos &D, int H, int W)
{
	/*
		가로 or 세로 길이가 홀수일 때 : 짝수행과 홀수행을 구분하여 출력

		─────┐   
		┌────┘ 
		└─────  
	*/
	if (H % 2 == 1 || W % 2 == 1)
	{
		for (int h = 0; h < H; ++h)
		{
			for (int w = 0; w < W - 1; ++w)
			{
				cout << (h % 2 == 0 ? 'R' : 'L');
			}

			if (h < H - 1)
			{
				cout << 'D';
			}
		}

		return;
	}

	/*
		가로/세로 길이가 모두 짝수일 때 
		: 주어진 데이터를 3구간으로 나누고, 
		[짝][홀] or [홀][짝]인 요소 중 최소값인 칸을 제외하고 지나간다.
		
		─────┐   // 1구간
		┌────┘ 
		└┐┌┐┌┐   // 2구간
		X└┘└┘│  
		┌────┘   // 3구간
		└─────  
	*/

	int part_D = D.x / 2;

	// 1구간
	for (int h = 0; h < part_D * 2; ++h)
	{
		for (int w = 0; w < W - 1; ++w)
		{
			cout << (h % 2 == 0 ? 'R' : 'L');
		}
        
		// 마지막 행이면 D를 붙이지 않음
		if (h < H - 1)
		{
			cout << 'D';
		}
	}

	// 2구간 
	{
		pos S = { part_D * 2, 0 };
		pos E = { part_D * 2 + 1, W - 1 };

		int dr_x[] = { 1, 0, -1, 0 };
		int dr_y[] = { 0, 1, 0, 1 };
		string move = "DRUR";
		int idx = 0;

		while (S.x != E.x || S.y != E.y)
		{
			int n_idx = idx % 4;
			int nx = S.x + dr_x[n_idx];
			int ny = S.y + dr_y[n_idx];

			if (nx == D.x && ny == D.y)
			{
				cout << 'R';
				S.y += 1;
			}
			else
			{
				cout << move[n_idx];
				S.x = nx;
				S.y = ny;
				++idx;
			}
		}

		// 마지막 행이면 D를 붙이지 않음
		if (part_D < H / 2 - 1)
		{
			cout << 'D';
		}
	}

	// 3구간
	for (int h = (part_D + 1) * 2; h < H; ++h)
	{
		for (int w = 0; w < W - 1; ++w)
		{
			cout << (h % 2 == 0 ? 'L' : 'R');
		}

		// 마지막 행이면 D를 붙이지 않음
		if (h < H - 1)
		{
			cout << 'D';
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int H, W;
	cin >> H >> W;
	vector<vector<int>> board(H, vector<int>(W));
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			cin >> board[i][j];
		}
	}

	pos D = {0, 1};
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			// [짝][홀] or [홀][짝]인 요소 중에서 최소값 찾기
			if ((i + j) % 2 == 1 && board[D.x][D.y] > board[i][j])
			{
				D = {i, j};
			}
		}
	}

	// [0][0] ~ [H - 1][W - 1]까지 기쁨을 합을 최대로 하는 경로 출력하기
	print_path(board, D, H, W);

	return 0;
}

 

 

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

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

 

최대한 많은 칸을 지나가면서 시작점~도착점까지의 경로를 구하는 문제이다.

 

이때 주어진 가로길이 or 세로길이 둘중 하나라도 홀수라면

주어진 칸 전체를 지나갈 수 있다. 

 

문제가 되는 것은 가로길이 & 세로길이가 둘다 짝수인 경우이다.

그림을 그려보면 알겠지만 이경우는 반드시 [짝][홀], [홀][짝]인 한칸을 제외할 수 밖에 없다.

기쁨의 합을 최대로 해야하므로, 값이 최소인 칸을 제외해야한다는 것은 금방 알 수 있다.

그런데 우리는 경로를 출력해야 한다...

 

 

따라서 이 경우, 주어진 맵을 3개의 구간으로 분류해야 한다.

열을 2줄씩 자른 것이 한 단위가 되고

최소값 X가 포함된 구간이 2구간, 그 위가 1구간, 그 아래가 3구간이다.

 

1구간과 3구간은 간단하게 구현할 수 있다.

1구간과 3구간은

최소값 X가 포함된 구간 전까지 or X를 지나고 나서 끝까지

RRRRD 또는 LLLLD를 단순 반복 출력해주면 된다.

 

 

문제는 또 2구간인데..

[짝][홀], [홀][짝]인 칸을 제외하는 경우의 경로를 모두 그려보았다.

그러면 한가지 패턴이 보인다.

 

 

길목에 X가 없다면 "DRUR"을 반복한다는 것이다!

중간에 X를 만난다면 R을 한번 출력하고 다시 DRUR패턴을 반복한다

아래코드는 4방향 이동시에 썼던 기법을 활용하여 구현한 코드이다.

pos S = { part_D * 2, 0 };
pos E = { part_D * 2 + 1, W - 1 };

int dr_x[] = { 1, 0, -1, 0 };
int dr_y[] = { 0, 1, 0, 1 };
string move = "DRUR";
int idx = 0;

while (S.x != E.x || S.y != E.y)
{
	int n_idx = idx % 4;
	int nx = S.x + dr_x[n_idx];
	int ny = S.y + dr_y[n_idx];

	if (nx == D.x && ny == D.y)
	{
		cout << 'R';
		S.y += 1;
	}
	else
	{
		cout << move[n_idx];
		S.x = nx;
		S.y = ny;
		++idx;
	}
}

 

 

이렇게 코드를 1구간, 2구간, 3구간의 순으로 출력하도록 구현해주면 된다