백준 2873 (롤러코스터)

문제

---

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

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

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

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

 

 

 

풀이

---

그리디 알고리즘 문제에 대한 어느정도의 감을 찾았다.

가장 중요한건 시간을 가지고 경우의 수를 생각하면서 코드화 시켜야한다는 것.

 

롤러코스터 문제의 경우에는 3가지 경우가 있다.(편하게 Row(행) 은 R, Column(열) 은 C 로 부르겠다)

• R이 홀수
• R이 짝수, C이 홀수
• R이 짝수, C이 짝수

이렇게 세가지 경우가 존재한다.

제일 핵심은 최대한 많은 칸을 지나야 최대 값을 가질 수 있다.

• R이 홀수인 경우

R,C 모두 홀수의 경우

R은 홀수 C는 짝수

위 와 같이 C의 값에 상관없이 ㄹ 자로 모든 칸을 훑을 수 있다.

 

• R이 짝수, C이 홀수인 경우

 

R 이 짝수고 C가 홀수인 경우도 위아래 지그재그 형태로 모든 칸을 훑을 수 있다.

 

• R이 짝수고 C가 짝수인 경우

가장 핵심이 되는 부분이다. 이경우는 모든 칸을 절대로 다 지나갈 수가 없다.

옆 그림과 같이 체스판 처럼 검정 하얀색을 칠했다.

 

이렇게 나타냈을 경우 하얀색을 지나지 않을 경우 최소 3칸을 지나지 못한다.( 이 경우는 직접 그림을 그려서 생각해 보길 바란다.)

 

검정 칸을 지나지 않을 경우 최소 1칸을 지나지 않고 끝점에 도달 할 수 있다.

검정칸 중 가장 작은 수를 제외하고 모든 수를 지나는 경우가 가장 최선이 되겠다.

 

 

이경우 2줄씩 검사하면서 지나가게 하였다.

1. 2행 안에 최소칸이 존재하지 않으면 ㄹ 자 형태로 모든 칸을 지나간다.
2. 2행 안에 최소칸이 존재할경우 최소칸을 제외한 모든칸을 위아래 지그재그 형태로 지날 수 있다.

우선 ㄹ자 형태로 모든칸을 지나는 함수다.

static void LeftAndRight(int c, int r, int start_c, int start_r) {
	for(int i = start_c ; i < c ; i++) {
		for(int j = 1 ; j < r ; j++) {
			if(((i % 2) + start_r) % 2 == 0) {
				sb.append("R");
			}
			else {
				sb.append("L");
			}
		}
		if(i != c - 1)
			sb.append("D");
	}
}
    

여기서 필자는 row 와 column 을 바꿔서 풀었다.. 이점을 감안하고 반대로 생각해주길 바란다. 코드에서 r 은 Column 값이고 c 값은 Row 값이다.

 

start_r 은 왼쪽부터 출발하는지 오른쪽부터 출발하는 지 구분하기 위한 값이다. 

 

 

위아래 지그재그 형태로 칸을 지나가는 함수다

static int UpAndDown(int min_c, int min_r, int c, int r, int start) {
		
		int last = 0;
		for(int i = 0; i < r ; i++) {
			for(int j = start ; j < c ; j++ ) {
				if(i == min_r && (j == min_c || j+1 == min_c)) {
					continue;
				}
				if(last % 2 == 0) {
					sb.append("D");
				}
				else {
					sb.append("U");
				}
			}
			
			if(min_r != i) {
				last++;
			}			
			if( i != r-1) {
				sb.append("R");
			}
		}
		if(min_c <= c  && min_r <= r) {
			return 1;
		}
		return 0;
	}

여기서 반환 값은 위아래 지그재그형태로 지나간 뒤는 왼쪽에서 오른쪽으로 지나가야 하기때문에 값을 주는것이다.

이는 UpAndDown 함수에서 start_r 값으로 사용된다.

last 라는 int 값을 두어 최소칸을 스킵해도 다음 줄에서 똑같은 방향으로 움직이게 했다.

 

< 전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	
	static int UpAndDown(int min_c, int min_r, int c, int r, int start) {
		
		int last = 0;
		for(int i = 0; i < r ; i++) {
			for(int j = start ; j < c ; j++ ) {
				if(i == min_r && (j == min_c || j+1 == min_c)) {
					continue;
				}
				if(last % 2 == 0) {
					sb.append("D");
				}
				else {
					sb.append("U");
				}
			}
			
			if(min_r != i) {
				last++;
			}			
			if( i != r-1) {
				sb.append("R");
			}
		}
		if(min_c <= c  && min_r <= r) {
			return 1;
		}
		return 0;
	}
	
	static void LeftAndRight(int c, int r, int start_c, int start_r) {
		for(int i = start_c ; i < c ; i++) {
			for(int j = 1 ; j < r ; j++) {
				if(((i % 2) + start_r) % 2 == 0) {
					sb.append("R");
				}
				else {
					sb.append("L");
				}
			}
			if(i != c - 1)
				sb.append("D");
		}
	}
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] RC = br.readLine().split("\\s");
		int c = Integer.parseInt(RC[0]);
		int r = Integer.parseInt(RC[1]);
		
		int[][] land = new int[c][r];
		int min = 1001, min_r = 1, min_c = 0;
		for(int i = 0 ; i < c ; i++) {
			String[] num = br.readLine().split("\\s");
			for(int j = 0 ; j < r ; j++) {
				land[i][j] = Integer.parseInt(num[j]);
				
				if((i % 2 == 0 && j % 2 == 1) || (i % 2 == 1  && j % 2 == 0)) {
					if((i == 0 && j == 1) || min > land[i][j]) {
						min = land[i][j];
						min_r = j;
						min_c = i; 
					}
				}
			}
		}
		
		
		if(c % 2 != 0) {
			LeftAndRight(c, r, 0, 0);
		}
		else {
			if(r % 2 != 0) {
				UpAndDown(c+1, r+1, c, r, 1);
			}
			else {
				int start_r = 0;
				for(int i = 0 ; i < c ; i += 2) {
					if(i == min_c || i+1 == min_c) {
						start_r = UpAndDown(min_c, min_r, i+1, r, i);
					}
					else {
						LeftAndRight(i+2 , r, i, start_r);
					}
					
					if(i != c - 2) {
						sb.append("D");
					}
				}
			}
		}
		
		System.out.println(sb);
	}
}