[P3] 백준 2873번 롤러코스터 C++ 구현, 그리디 알고리즘, 홀짝성, 해 구성하기

리뷰

 

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

간만에 풀어본 조금 빡센 구현문제

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. 변수 r, c를 초기화 하고, 값을 입력 받는다.
2. 변수 mn을 1000으로, px, py를 -1로 초기화한다.
3. r*c크기의 순회하며 변수 d에 기쁨 수치를 입력 받는다.
4. 현재 격자 인덱스의 합이 홀수면서 d가 mn보다 작을 경우 mn을 d로 변경하고, px, py에 좌표를 저장한다.
5. 변수 ans를 빈 문자열로 초기화한다.
6. 만약 행이 홀수개라면 위쪽부터 좌우 지그재그로 내려오는 문자를 ans에 추가해준다.
7. 만약 열이 홀수개라면 위쪽부터 상하 지그재그로 내려오는 문자를 ans에 추가해준다.
8. 행과 열이 모두 짝수개라면 별도의 분기 처리를 수행해준다.
9. 변수 f에 피해야할 좌표 이전까지의 행들에 대해 좌우 지그재그로 내려오는 문자를 저장한다.
10. 변수 m에 피해야할 좌표를 피하면서 왼쪽 위부터 오른쪽 아래까지 도달하는 경로를 저장한다.
11. 변수 b에 피해야할 좌표 이후부터 오른쪽 아래까지 좌우 지그재그로 나려오는 문자를 저장한다.
12. ans에 f + m + b값을 더해준다.
13. ans의 맨 뒤엔 도달 이후의 문자가 하나 추가되어 있으므로 pop_back()처리 후 출력해 준다.

 

트러블 슈팅

1. 열이 홀수인 경우를 행이 홀수인 경우를 그대로 복붙해 사용해 논리적 오류가 있어 WA를 받았다.
2. 열이 홀수인 경우 열을 순회하고, 홀수 열인 경우 'U', 짝수 열인 경우 'D'를 삽입해 AC를 받았다.

 

참고 사항

1. 행/열 중 하나라도 홀수인 경우 모든 지점을 방문할 수 있다.
2. 행/열이 모두 짝수인 경우 0-based-indexing기준 좌표 인덱스의 합이 홀수인 가장 작은 값을 미방문 하면 된다.
3. 2번의 경우 2개 행을 짝지어서 구현해 주면 된다.

 

정답 코드

#include<iostream>
using namespace std;

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

	int r, c; cin >> r >> c;
	int mn = 1000;
	int px = -1, py = -1;
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			int d; cin >> d;
			if ((i + j) % 2 && d < mn) {
				mn = d;
				px = i, py = j;
			}
		}
	}

	string ans = "";
	if (r % 2) {
		for (int i = 0; i < r; ++i) {
			if (i % 2) ans += string(c - 1, 'L') + "D";
			else ans += string(c - 1, 'R') + "D";
		}
	}
	else if (c % 2) {
		for (int i = 0; i < c; ++i) {
			if (i % 2) ans += string(r - 1, 'U') + "R";
			else ans += string(r - 1, 'D') + "R";
		}
	}
	else {
		string f = "";
		for (int i = 0; i < px / 2; ++i) {
			f += string(c - 1, 'R') + "D";
			f += string(c - 1, 'L') + "D";
		}

		string m = "";
		bool flag = px % 2 ? true : false;
		int cx = px - flag, cy = 0;
		
		while (cx % 2 == 0 || cy != c - 1) {
			//cout << cx << " " << cy << "\n";
			if ((cx == px && cy + 1 == py)) {
				if (cx % 2) {
					--cx;
					m += "U";
				}
				else {
					++cx;
					m += "D";
				}
			}
			else if (cy == py || (!m.empty() && (m.back() == 'U' || m.back() == 'D'))) {
				++cy;
				m += "R";
			}
			else if ((!m.empty() && m.back() == 'R')) {
				if (cx % 2) {
					--cx;
					m += "U";
				}
				else {
					++cx;
					m += "D";
				}
			}
			else if (m.empty()) {
				++cx;
				m += "D";
			}
		}
		m += "D";

		string b = "";
		for (int i = (px + 2) / 2; i < r / 2; ++i) {
			b += string(c - 1, 'L') + "D";
			b += string(c - 1, 'R') + "D";
		}

		//cout << "f:" << f << " m:" << m << " b:" << b << "\n";
		ans += f + m + b;
	}
	ans.pop_back();
	cout << ans;
}