[자바] 백준 2873 - 롤러코스터 (java)

 문제 : boj2873

---

 

필요 알고리즘 개념

• 구성적, 그리디
  
  • 정규화된 방식 없이 이 문제만을 위한 규칙이 필요한 구성적 문제이다. 또한 그리디를 적용해 해당 규칙을 정할 수 있긴하다(?).
• 구현
  
  • 보통 플래급에서 '구현'이 태그로 있다는건 구현이 엄청 어렵다는 뜻이다 ㅋㅋ

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  사실 규칙자체는 여러 케이스에 대해 마구 그려보면서 머리로 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 문제는 그걸 알았다고 해도 구현이 쉽지 않다는 점이다. 물론 구현으로 악명높은 RPG Extreme 보다는 훨씬 덜하다.

 

  아무튼 규칙부터 한번 생각해보자.

우선 R또는 C가 홀수인 경우엔(둘 다 홀수여도 마찬가지) 그냥 모든 칸을 다 갈 수 있다. 이건 누구라도 쉽게 찾았을거다.

 

  이제 R, C 둘다 짝수일때가 문제이다. 내가 찾은 규칙은 시작점에서 맨허튼 거리(manhattan distance, 택시 거리(taxicab geometry)와 동일) 기준으로 홀수인걸 제거하면 해당 위치 하나만 빼고 나머지 모두를 갈 수 있으므로 맨허튼 거리 기준으로 홀수인 곳 중 가장 숫자가 낮은것 중 아무거나 하나를 선택해서 거기만 제외하면 된다는 규칙이다. 즉, 해당 위치가 (i, j)일 경우 i+j가 홀수인 곳 중 가장 낮은 값을 가진곳을 제외하면 된다. 참고로 맨허튼 거리 기준 짝수인건 생각을 안해도 되는게, 짝수인 곳이 빠질 때 무조건 인접한 홀수인 곳도 하나 이상 빠질 수 밖에 없다. 따라서 홀수인 곳 하나만 제거하는게 무조건 최선이다.

 

  그럼 이제 한 곳을 정한 후 방향(U,R,L,D) 출력을 위해 어떻게 가면 매번 한 곳을 제외하고 전부 갈 수 있을지 생각해보자.

1. 행과 열을 각각 2줄씩 나눈다.

2. 우선 행을 기준으로 선택한 지점이 포함된 2줄짜리 행이 오기 전까지는 우측으로 쭉 -> 아래로 한칸 -> 좌측으로 쭉을 진행한다.

3. 해당 지점이 포함된 2줄짜리 행에 대해서는 세로로 움직이면서 해당 지점을 피한다.

4. 이후 남은 행이 있다면, 이번엔 우측 위에서 시작되므로 좌측으로 쭉 -> 아래로 한칸 -> 우측으로 쭉을 반복한다.

 

  위는 4X4라 좀 헷갈릴 수 있으니 좀 더 큰걸로 다시 보자.

 

  문제는 규칙을 찾았다고 해도 구현이 상당히 어려울 수 있다는 점이다. 화이팅(?)

 

팁 : 풀고나서 난이도 기여쪽 의견을 보면 구현에 대한 한탄과, 스파게티 코드에 대한 내용들이 있어서 읽기 재밌다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int LIMIT = 1000;
    StringBuilder sb = new StringBuilder();

    private void printType1(int c) {
        for (int i = 0; i < c-1; i++) sb.append('R');
        sb.append('D');
        for (int i = 0; i < c-1; i++) sb.append('L');
        sb.append('D');
    }

    private void printType2(int r) {
        for (int i = 0; i < r-1; i++) sb.append('D');
        sb.append('R');
        for (int i = 0; i < r-1; i++) sb.append('U');
        sb.append('R');
    }

    private void printType3(int c) {
        for (int i = 0; i < c-1; i++) sb.append('L');
        sb.append('D');
        for (int i = 0; i < c-1; i++) sb.append('R');
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        if (r%2==1) {
            for (int i = 0; i < r/2; i++) printType1(c);
            for (int i = 0; i < c-1; i++) sb.append('R');
            System.out.println(sb);
            return;
        }
        if (c%2==1) {
            for (int i = 0; i < c/2; i++) printType2(r);
            for (int i = 0; i < r-1; i++) sb.append('D');
            System.out.println(sb);
            return;
        }

        // both r and c are even
        int tr = 0, tc = 0;
        int min = LIMIT;
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                int cur = Integer.parseInt(st.nextToken());
                if ((i+j)%2==0 || min <= cur) continue;
                min = cur;
                tr = i+1;
                tc = j+1;
            }
        }

        // A
        for (int i = 0; i < (tr-1)/2; i++) printType1(c);

        // B
        for (int i = 0; i < (tc-1)/2; i++)
            sb.append('D').append('R').append('U').append('R');
        if (tr%2==1)
            sb.append('D').append('R');
        else
            sb.append('R').append('D');

        int len = (c-tc)/2;
        if (len != 0)
            sb.append('R');
        for (int i = 0; i < len; i++) {
            sb.append('U').append('R').append('D');
            if (i != len-1)
                sb.append('R');
        }

        // C
        len = (r-tr)/2;
        if (len != 0) {
            sb.append('D');
        }
        for (int i = 0; i < len; i++) {
            printType3(c);
            if (i != len-1)
                sb.append('D');
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}