백준 2873 롤러코스터 Java

정답률 29퍼센트의 그리디 문제이다. 

매우 어려운 문제인 것 같고 어려워서 금방 까먹을 것 같기 때문에 백준님의 강의를 통해 정리하려 한다.

 

r행 c열의 표 모양에서 가장 왼쪽  위 칸 부터 가장 오른쪽 아래 칸 까지

방문하는 점수의 합이 최대로 가는 경로를 출력하면 된다.

방문하지 않은 칸이 있어도 된다.

 

물론 전부 다 방문하는게 최고로 좋다.

이런 식으로 전부 다 방문하거나

이런 식으로 전부 다 방문할 수 있다.

 

하지만 왼쪽 가장 위부터 오른쪽 가장 아래까지 전부 다 방문할 수 없는 경우가 존재한다.

백준님의 강의자료 중..

행과 열의 길이가  둘 다 짝수 인경우에는 절대 전부 다 방문할 수가 없다.

행과 열 둘 중 하나라도 홀수라면 전부 다 방문 할 수 있다.

 

 

위의 행렬을 체스판이라고 생각하면

행과 열이 모두 짝수인 경우엔

시작점과 도착점이 모두 흰색이다.

(행과 열중 하나라도 홀수인 경우엔 시작점 흰색, 도착점 검은색형태를 띈다.)

 

흰->검->흰->검->흰 이런 식으로 (흰3 검2)

흰색으로 시작해서 흰색으로 끝나야 하기 때문에

흰색의 수가 검정색의 수보다 하나 많아야

모든 칸을 방문할 수 있다.

하지만 행과 열이 짝수인 경우엔

흰색과 검정색의 수가 같기 때문에

흰색의 수를 하나 늘리거나 검정색의 수를 하나 없애야만 모든 칸을 방문할 수 있다.

이 문제는 행렬이 주어지기 때문에 흰색의 수를 하나 늘리는것은 불가능 하므로

검정색 칸을 하나 방문하지 않는 것으로 흰색의 수를 검정색의 수보다 하나 많게 할 수 있다.

따라서 가장 점수가 낮은 검정칸 하나를 빼고 방문하면 가장 큰 점수를 만들어 낼 수 있다.

 

하지만 문제는 점수를 출력하는 것이 아니라 경로를 출력하는 것이다.

행과 열중 하나라도 홀수 인 경우엔

이런식으로 모든 칸을 방문한 경로를 출력하면 되고

 

행과 열 둘다 짝수인 경우엔

문제를 살짝 변형해서 풀어야 한다.

시작점과 도착점에서 각자 출발해서 서로 만날 때까지 이동하는 문제로.

 

검정 칸중 가장 낮은 점수를 검은 칸으로 표시해 두고

시작점과 도착점의 인접한 행 2줄을 비교하여 검은칸이 없다면

그 경로를 StringBuilder에 우선 저장한다.

 

그 다음 시작점 A는 인접한 행 2줄에서 검은 칸이 있기 때문에 가만히 있고

B는 인접한 행 2줄에 아무것도 없기 때문에 또 그 경로를 스트링빌더에 저장한다.

 

이런식으로 가다보면

행의 크기는 언젠가 2가 되게 된다.

그러면 똑같은 방식으로 이번에는 열을 2칸씩 비교해서 그 경로를 저장한다.

그렇게 쭉쭉 해나가다 보면 언젠간 무조건 두 가지의 경우로 남게 된다.

왼쪽 경우                                     오른쪽 경우

그림처럼 경로를 다시 빌더에 저장하면 된다.

시작점과 도착점에서 따로 출발하기 때문에

StringBuilder를 2개 만들어서

따로 저장하고 도착점에서 출발하는 경우엔

다 저장하고 역순으로 시작점 빌더에 이어주서 출력해주면 된다.

 

import java.util.Scanner;
 
public class Q2873 {
    
    public static void append(StringBuilder s, char c, int cnt) { //cnt만큼 스트링빌더에 char c를 삽입하는 메소드
        for (int i=0; i<cnt; i++) {
            s.append(c);
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        StringBuilder s = new StringBuilder();
        if (n%2 == 1) { //n이 홀수인경우
            for (int i=0; i<n; i++) {
                if (i%2 == 0) {
                    append(s, 'R', m-1);
                    if (i != n-1) {
                        append(s, 'D', 1);
                    }
                } 
                else {
                    append(s, 'L', m-1);
                    append(s, 'D', 1);
                }
            }
        }
        else if (m%2 == 1) { //m이 홀수인 경우
            for (int j=0; j<m; j++) {
                if (j%2 == 0) {
                    append(s, 'D', n-1);
                    if (j != m-1) {
                        append(s, 'R', 1);
                    }
                } else {
                    append(s, 'U', n-1);
                    append(s, 'R', 1);
                }
            }
        }
        else { //n과m이 둘다 짝수인 경우
            int x, y;
            x = 0;
            y = 1;
            for (int i=0; i<n; i++) { //검정칸 중 젤 작은 수를 찾는다.
                for (int j=0; j<m; j++) {
                    if ((i+j)%2 == 1) {
                        if (a[x][y] > a[i][j]) {
                            x = i;
                            y = j;
                        }
                    }
                }
            }
            int x1 = 0;
            int y1 = 0;
            int x2 = n-1;
            int y2 = m-1;
            StringBuilder s2 = new StringBuilder();
            while (x2 - x1 > 1) { //시작점과 도착점에서 인접한 2줄 검정칸이 없다면 지우기
                if (x1/2 < x/2) {
                    append(s, 'R', m-1);
                    append(s, 'D', 1);
                    append(s, 'L', m-1);
                    append(s, 'D', 1);
                    x1 += 2;
                }
                if (x/2 < x2/2) {
                    append(s2, 'R', m-1);
                    append(s2, 'D', 1);
                    append(s2, 'L', m-1);
                    append(s2, 'D', 1);
                    x2 -= 2;
                }
            }
            while (y2 - y1 > 1) { //2줄 남았을 경우 인접한 2칸에서 검정칸이 없다면 지우기
                if (y1/2 < y/2) {
                    append(s, 'D', 1);
                    append(s, 'R', 1);
                    append(s, 'U', 1);
                    append(s, 'R', 1);
                    y1 += 2;
                }
                if (y/2 < y2/2) {
                    append(s2, 'D', 1);
                    append(s2, 'R', 1);
                    append(s2, 'U', 1);
                    append(s2, 'R', 1);
                    y2 -= 2;
                }
            }
            if (y == y1) { //2x2칸 남았을 경우
                append(s, 'R', 1);
                append(s, 'D', 1);
            } else {
                append(s, 'D', 1);
                append(s, 'R', 1);
            }
            s2.reverse(); //도착점에서 출발한 경로 뒤집기
            s.append(s2);
        }
 
        System.out.println(s);
    }
}