[BJ15684] 사다리 조작

🚩 문제 설명

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

◾ 최소로 가로선을 놓아서 i번째 사다리가 다시 제 자리로 돌아오는지 확인하는 문제

◾ 총 3개의 가로선까지 놓을 수 있다. 그 이상은 -1 로 처리.

 

 

 

---

 

 

 

✅ 입출력

변수 설명
N: 세로선의 개수
M: 이미 그려져있는 가로선의 개수
H: 가로선의 개수
return ➡️ i번째 사다리에서 시작해서 i번째 사다리로 오게하기 위하여 놓을 수 있는 최소 가로선의 개수

✔️ 예제 1

2 0 3

0

✔️ 예제 2

5 5 6
1 1
3 2
2 3
5 1
5 4

3

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

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


public class Main {
	static int ans, N, M, H;
	static int[][] ladder;


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		ans = Integer.MAX_VALUE;
		ladder = new int[H + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			ladder[a][b] = 1; // 오른쪽으로 이동
			ladder[a][b + 1] = 2; // 왼쪽으로 이동
		}

		// 완전탐색
		for (int i = 0; i <= 3; i++) dfs(0, i);

		// 3개 이상이거나, 불가능한 경우
		if (ans == Integer.MAX_VALUE) ans = -1;

		// 출력
		System.out.println(ans);

	} // end main


	private static void dfs(int dep, int cnt) {
		if (dep == cnt) {
			if (check()) ans = Math.min(ans, dep);
			return;
		}

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (ladder[i][j] != 0) continue;
				if (ladder[i][j + 1] != 0) continue;

				ladder[i][j] = 1;
				ladder[i][j + 1] = 2;
				dfs(dep + 1, cnt);
				ladder[i][j] = 0;
				ladder[i][j + 1] = 0;
			}

		}

	} // end dfs


	// i -> i 번째로 가는지 확인하는 함수
	private static boolean check() {
		// 열(x)을 기준으로 훑어본다.
		// 행(y)을 따라 내려가며 0이 아닌 숫자가 있는지 확인한다. 다른 사다리로 넘어가는 지점.
        
		for (int i = 1; i <= N; i++) {
			int y = 1;
			int x = i;
			while (y <= H) {
				if (ladder[y][x] == 1) x++;
				else if (ladder[y][x] == 2) x--;
				y++;
			}

			if (x != i) return false;
		}

		return true;
	} // end check
}

💬 Point

➡️  백트랙킹
➡️  3개 이상의 가로선은 놓지 못한다.
➡️ 사다리를 타서 자기 자신으로 돌아오는지 확인을 해야한다.
➡️ 사다리를 탈 때, 오른쪽으로 가는지 왼쪽으로 가는지 표시

◾ 백트랙킹을 이용하여 풀 수 있는 문제이다.

◾ 백트랙킹 까지는 아이디어가 닿았으나, 사다리를 좌우로 타는 것을 따로 표시하는 데 까지는 생각하지 못했다.

 

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

    ladder[a][b] = 1; // 오른쪽으로 이동
    ladder[a][b + 1] = 2; // 왼쪽으로 이동
}

◾ 오른쪽으로 이동하는 사다리는 1로, 왼쪽으로 이동하는 사다리는 2로 표시했다.

 

// 완전탐색
for (int i = 0; i <= 3; i++) dfs(0, i);

◾ 놓을 수 있는 사다리는 0개에서 부터 3개까지.

◾ 각 개수가 최종 dep 가 된다. 즉슨, 0 depth 부터 3 depth 까지 돌도록 반복문을 돌아 dfs 를 하여 ans 의 min 값을 구한다.

 

private static void dfs(int dep, int cnt) {
    if (dep == cnt) {
        if (check()) ans = Math.min(ans, dep);
        return;
    }

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j < N; j++) {
            // 사다리를 이미 놓은 곳은 가지 않는다. 
            if (ladder[i][j] != 0) continue;
            if (ladder[i][j + 1] != 0) continue;

            // 사다리를 놓는다. 
            ladder[i][j] = 1;
            ladder[i][j + 1] = 2;
            dfs(dep + 1, cnt);
            ladder[i][j] = 0;
            ladder[i][j + 1] = 0;
        }

    }

} // end dfs

◾ 백트랙킹을 돈다.

◾ 백트랙킹을 돌 때, 갈 수 없는 곳 -> 즉슨 조건에 맞지 않은 곳은 continue 처리를 해야한다.

◾ 위에서는 만약 사다리를 이미 놓은곳이라면 continue 을 한다.

◾ 그게 아니라면 사다리를 놓는다.

◾ 만약 dep 가 최종 cnt 가 되면 기저조건이 되어 빠져나온다. 그때, 자기 자신으로 가는 사다리인지 확인한다. 

 

// i -> i 번째로 가는지 확인하는 함수
private static boolean check() {
    // 열(x)을 기준으로 훑어본다.
    // 행(y)을 따라 내려가며 0이 아닌 숫자가 있는지 확인한다. 다른 사다리로 넘어가는 지점.
    for (int i = 1; i <= N; i++) {

        int y = 1;
        int x = i;
        while (y <= H) {
            if (ladder[y][x] == 1) x++;
            else if (ladder[y][x] == 2) x--;
            y++;
        }

        if (x != i) return false;
    }

    return true;
} // end check

◾ 열을 기준으로 하나씩 볼 것이다. (1부터 끝까지 각 사다리로 돌아오는지 확인.)

◾ 그리고 행을 따라 내려가면서 0이 아닌 것을 만나면 (즉, 옆을 타고가는 사다리를 만나면) 타고간다.

◾ 1 을 만나면 오른쪽으로 타고가고

◾ 2 를 만나면 왼쪽으로 타고간다.

◾ 만약, 처음의 번호와 타고 내려온 사다리의 열 번호가 다르다면 return false 한다. (처음 타고온 번호는 i에 저장되어 있다.)

◾ 만약 return false 을 타지 않는다면 모두 충족한 것이기 때문에 return true 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

# 백준 사다리타기 자바

# 백준 사다리타기 java

---