[Platinum III] 롤러코스터 - 2873
성능 요약
메모리: 73500 KB, 시간: 696 ms
분류
해 구성하기, 그리디 알고리즘, 구현
제출 일자
2025년 1월 6일 20:36:02
문제 설명
상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.
어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.
이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.
출력
첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.
문제 풀이
처음엔 짝수x짝수부분을 dfs로 풀었는데 시간초과가 났다. 이에 내가 생각하는 최적의 패턴이 존재했기에 이대로 출력해야겠다고 생각했고, 효율적인 계산을 위해 2묶음(행단위)으로 나눠 처리해줬다.
2차원배열을 마음대로 다루는 연습이 되었다.
코드
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int R, C, board[][], res;
static int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
static String[] dir = {"R", "D", "L", "U"};
static boolean[][] visited;
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new int[R][C];
visited = new boolean[R][C];
for(int i=0; i<R; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<C; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
boolean flag = false; // 모두 순회해도 되면 true, 안되면(짝수 x 짝수) false
flag = !(R%2==0 && C%2==0);
if(flag) findAll();
else findExceptMin();
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
private void findExceptMin() {
int min = Integer.MAX_VALUE;
int minR = -1, minC = -1;
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if((i+j)%2 == 1 && board[i][j] < min) {
min = board[i][j];
minR = i;
minC = j;
}
}
}
for(int i=0; i<minR/2; i++) {
// 첫 행은 오른쪽으로
for(int j=0; j<C-1; j++) {
sb.append("R");
}
sb.append("D");
// 두번째 행은 왼쪽으로
for(int j=0; j<C-1; j++) {
sb.append("L");
}
sb.append("D");
}
int c = 0;
int r = 2 * (minR/2); // 최솟값 존재 묶음 중 윗줄
int nextR = r+1; // 최솟값 존재 묶음 중 아랫줄
while(r != nextR || c != C-1) {
if(r < nextR && (c != minC || nextR != minR)) {
r++;
sb.append("D");
}
else if(r == nextR && (c != minC || nextR-1 != minR)) {
r--;
sb.append("U");
}
if(c != C-1) {
c++;
sb.append("R");
}
}
// 남은 묶음들
for(int i=minR/2+1; i<R/2; i++) {
sb.append("D");
for(int j=0; j<C-1; j++) {
sb.append("L");
}
sb.append("D");
for(int j=0; j<C-1; j++) {
sb.append("R");
}
}
// visited[minR][minC] = true;
// dfs(0, 0, 1);
}
// private boolean dfs(int r, int c, int cnt) { // 시간초과
// if(r == R-1 && c == C-1) return cnt == R * C - 1;
//
// visited[r][c] = true;
//
// for(int k=0; k<4; k++) {
// int nr = r + dr[k];
// int nc = c + dc[k];
//
// if(nr >= 0 && nr < R && nc >= 0 && nc < C && !visited[nr][nc]) {
// sb.append(dir[k]);
// if(dfs(nr, nc, cnt + 1)) return true;
// sb.setLength(sb.length()-1);
// }
// }
//
// visited[r][c] = false;
// return false;
// }
private void findAll() {
if(R % 2 == 1) {
for(int i=1; i<=R; i++) {
if(i%2 == 1) {
for(int j=0; j<C-1; j++) {
sb.append("R");
}
}
else {
for(int j=0; j<C-1; j++) {
sb.append("L");
}
}
if(i != R) sb.append("D");
}
}
else {
for(int j=1; j<=C; j++) {
if(j%2 == 1) {
for(int i=0; i<R-1; i++ ) {
sb.append("D");
}
}
else {
for(int i=0; i<R-1; i++ ) {
sb.append("U");
}
}
if(j!=C) sb.append("R");
}
}
}
}