[백준] 15684. 사다리 조작 (Java)

 

15684번: 사다리 조작

 

풀이

• 사다리를 코드로 어떻게 표현해야 할지 고민을 엄청 한 문제!!
• method를 기능별로 만들어서 풀었더니 군더더기 없이 한번에 통과!

---

• 이차원 배열을 만들고 한 column을 한 세로선이라고 두었다.
• 그리고 가로선은 인덱스 값을 줘서 표시했다.
  • 이렇게 한 이유는 만약 1로만 표시하면 내려갈 때 양 옆에 가로선이 존재하면 이게 옆동네 가로선인지 내 가로선인지 알 길이 없다.
  • 따라서 내 가로선인지 바로 구분하기 위해 인덱스를 두었다.

 

예제 입력 7을 위에서 말한대로 하면 이렇게 된다.

 

• 가로선은 3개가 넘어가면 -1을 출력하기 때문에 1~3개를 놓는 모든 방법에 대해 브루트포스를 돌렸다. - 조합과 백트래킹을 이용하면 된다.
• 사다리 세로선 하나를 잡고 내려가는 method를 반목문으로 세로선 개수만큼 돌려서 만약 i != i가 하나라도 나오면 false로 체크하고 바로 다음 사다리 개수로 넘어가는 방식으로 했다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, H, ans = -1; // H: row, N: column
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H + 1][N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = i + 1;
            map[x][y + 1] = i + 1;
        }

        if (result()) ans = 0;

        for (int i = 1; i <= 3; i++) {
            if (ans > -1) break;
            installLadder(0, i);
        }

        bw.write(String.valueOf(ans));
        br.close();
        bw.close();
    }

    public static void installLadder(int cnt, int L) {
        if (cnt == L) {
            if (result()) ans = L;
            return;
        }

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j < N; j++) {
                if (map[i][j] != 0 || map[i][j + 1] != 0) continue;
                map[i][j] = (M + 1) + cnt;
                map[i][j + 1] = (M + 1) + cnt;
                installLadder(cnt + 1, L);
                map[i][j] = 0;
                map[i][j + 1] = 0;
            }
        }
    }

    // i -> i로 가는지 체크
    public static boolean result() {
        for (int j = 1; j <= N; j++)
            if (!explore(j)) return false;
        return true;
    }

    // 한 세로선에 대해 내려가는 동작 수행
    public static boolean explore(int start) {
        int x = 0;
        int y = start;

        while (x < H) {
            if (map[x + 1][y] > 0) {
                int ladderIdx = map[x + 1][y];
                if (y > 1 && map[x + 1][y - 1] == ladderIdx) y--;
                else if (y < N && map[x + 1][y + 1] == ladderIdx) y++;
            }
            x++;
        }

        if (y == start) return true;
        return false;
    }
}