[Algorithm] SW 기출문제 - 사다리 조작(15684) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 사다리 조작 문제를 해결하는 과정을 작성하고자 합니다.

사다리 조작 문제는 해결법을 찾지 못하여 다른 블로그 분의 코드를 참조하였습니다.

 

문제 출처: https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

 

1. 풀이 소스:

 

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int h = parseInt(st.nextToken());

        Ladder ladder = new Ladder(n, h);
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            ladder.setMap(parseInt(st.nextToken()), parseInt(st.nextToken()));
        }

        ladder.start();
        System.out.println(ladder.getMinAddEdge());
    }
}

class Ladder {
    int n; // 열 개수
    int h; // 행 개수
    int[][] map;
    int minAddEdgeCnt = 4; // 최소 추가 설치 사다리 개수 (만약 4가 바뀌지 않는다면 -1)

    Ladder (int n, int h) {
        this.n = n;
        this.h = h;
        map = new int[h + 2][n + 2]; // (1, 1)  ~ (h ~ )이므로 h + 2
    }

    void setMap(int row, int col) {
        map[row][col] = 1;
    }

    void start() {
        for (int i = 0; i <= 3; i++) dfs(0, i, 1); // dfs로 추가 사다리가 0인 것부터 0 ~ 3까지 탐색
    }

    void dfs(int cnt, int limit, int r) {
        if (cnt > limit || cnt > minAddEdgeCnt) return; // 만약 추가한 사다리가 한계치 (0 ~ 3)으로 설정한 값보다 크거나 최대치를 넘는다면 종료

        if (isPossible()) {
            minAddEdgeCnt = Math.min(minAddEdgeCnt, cnt);
            return;
        }

        for (int row = r; row <= h; row++) { // 각 몇번째 행에서부터
            for (int col = 1; col <= n; col++) { // 1번열 (1, 1) ~ n개까지 (총 n개의 열)
                if (map[row][col] == 0 && map[row][col - 1] == 0 && map[row][col + 1] == 0) { // 참조 #1
                    map[row][col] = 1; //  현재 열 선택 가능
                    dfs(cnt + 1, limit, row); // 사다리를 하나 추가하여 이어서 dfs 진행
                    map[row][col] = 0; // dfs 종료 후 다시 이전에 설정한 1을 초기화
                }
            }
        }
    }

    boolean isPossible() {
        for (int col = 1; col <= n; col++) {
            int nowC = col; // 현재 선택한 열 번호
            int row = 1; // 행의 시작은 1
            while (true) {
                if (row > h) break; // 만약 h의 길이보다 크다면
                if (map[row][nowC] == 1) nowC++; // 1이라면 오른쪽으로 연결
                else if (map[row][nowC - 1] == 1) nowC--;// 이전항이 1이라면 이전항에서 연결한 것임
                row++; // 한번 이동했다면 그 열에서는 연속적으로 다음 열로 이동할 수 없기에 바로 내려갈 수 있음
            }

            if (nowC != col) return false; // 만약 열을 이동하고 최종적으로 마지막 행을 지나 도착했을 때, 이전 열과 다르다면
        }
        return true;
    }


    int getMinAddEdge() {
        return minAddEdgeCnt == 4 ? -1 : minAddEdgeCnt;
    }
}

 

 

2. 풀이 중점 사항

 

참조#1

 

이 문제는 사다리를 조작할 때, 0 ~ 3가지의 사다리를 어떻게 놓을 것인가가 관건이었습니다. 같은 행의 하나의 열 B는 인접한 A와 C열에 동시에 사다리가 놓일 수 없습니다. 

 

즉    A      B      C

        |  ---  |  --- | 

 

이러한 식으로, 사다리를 놓을 수 없습니다. 

 

if (map[row][col] == 0 && map[row][col - 1] == 0 && map[row][col + 1] == 0) { // 참조 #1

 

이 소스가 의미하는 바는 만약 col이 B라고 가정하면, B보다 열 인덱스가 하나 작은 A열과 인덱스가 하나 큰 C 열의 값이 모두 0일 때만 map[row][col] = 1로 사다리를 놓을 수 있습니다.

map[row][col] = 1 이 의미하는 바는, col 열과 인접한 col + 1번 열에 사다리를 놓겠다는 의미입니다.

 

if map[row][col - 1] == 1이라면 col - 1와  인접한 인덱스가 하나 큰 col에 사다리를 놓았다는 것을 의미하므로

같은 행에 하나의 열은 두 개의 사다리를 놓을 수 없다라는 원칙에 위배되게 됩니다.

 

반대로 만약

if map[row][col + 1] == 1 이라면, 이 것은 col + 1 열과 인접한 col + 2에 사다리를 놓겠다는 것을 의미합니다. 만약 map[row][col] 이 사다리를 놓게 된다면 col + 1은 이 사다리를 공유하게 되는데, 이미 col + 1과 col + 2가 사다리를 하나 공유하고 있으므로
이 또한, 같은 행에 하나의 열은 두 개의 사다리를 놓을 수 없다는 원칙에 위배되게 됩니다.

 

따라서, 자신의 열과 인접한 두 열을 함께 비교해야 합니다.

(그러므로 h + 2 개로 초기화 map을 설정한 것과 일맥 상통합니다)

 

 

참조 #2

 

boolean isPossible() { // 참조#2
    for (int col = 1; col <= n; col++) {
        int nowC = col; // 현재 선택한 열 번호
        int row = 1; // 행의 시작은 1
        while (true) {
            if (row > h) break; // 만약 h의 길이보다 크다면
            if (map[row][nowC] == 1) nowC++; // 1이라면 오른쪽으로 연결
            else if (map[row][nowC - 1] == 1) nowC--;// 이전항이 1이라면 이전항에서 연결한 것임
            row++; // 한번 이동했다면 그 열에서는 연속적으로 다음 열로 이동할 수 없기에 바로 내려갈 수 있음
        }

        if (nowC != col) return false; // 만약 열을 이동하고 최종적으로 마지막 행을 지나 도착했을 때, 이전 열과 다르다면
    }
    return true;
}

 

이 코드와 비교하여 제가 이전에 실수했던 부분은, row++를 else에 넣었다는 점입니다.

문제는 nowC는 컬럼의 이동을 의미하는데, 같은 행의 열은 두 개의 사다리를 가질 수 없습니다.

즉 한 번 좌 혹은 우로 이동했다면 혹은 하지 않았다면 이는 곧바로 행을 한 칸 내려가야 한다는 것을 의미합니다.

 

즉      A      B      C

 1       |  ---  |       | 

 2       |       |        |

 3       |       |        |

 

만약 1행 B에서 출발하였다면 A와 사다리가 연결되어 있어서 A 열로 이동하고 1행 1열에서 2행 1열로 내려야 하는 것입니다.

만약 내리지 않는다면, 무한 루프에 빠지게 됩니다.

 

자세한 코드는 주석으로 처리하였습니다.

이상으로 백준 SW 기출문제 사다리 조작 문제 풀이를 마치도록 하겠습니다.

감사합니다.!!!

 

참고 자료: https://suhyeokeee.tistory.com/119