[백준]JAVA - 15684번: 사다리 조작

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

15684번: 사다리 조작

풀이

입력하는 과정에서 가로선 정보를 2차원 배열 map[][]에 3가지 경우로 나눠서 입력해줬다.

0: 해당 칸에는 가로선이 없음

1: 해당 칸에서 오른쪽으로 연결되는 선이 존재함

2: 해당 칸에서 왼쪽으로 연결되는 선이 존재함

 

해당 문제는 3개 이하의 가로선을 만들어서 i번에서 출발하면  i번으로 도착하게 만드는 문제다.

3개 이하의 가로선을 만들어야하기 때문에 dfs를 돌릴 때 limit 함수를 추가해줬다.

for (int i=0; i<4; i++) {
    limit = i;
    dfs(0);
            
    if (isBreak) break;
}
 
public static void dfs(int cnt) {
    if (isBreak) return;
        
    if (limit == cnt) {
        if (Check()) {
            isBreak = true;
        }
        
        return;
    }
        
    for (int i=1; i<H+1; i++) {
        for (int j=1; j<N; j++) {
            if (map[i][j] == 0 && map[i][j+1] == 0) {
                
                // 백트래킹
                map[i][j] = 1;
                map[i][j+1] = 2;
                    
                dfs(cnt+1);
                    
                map[i][j] = 0;
                map[i][j+1] = 0;
            }
        }
    }
}

dfs에서는 첫번째 세로선부터 가로선을 하나씩 추가해본다. 임의의 가로선을 추가하는 과정에서 똑같은 배열을 사용하기 때문에 백트래킹은 필수다.

 

계속 가로선을 추가해주면서 i번째 출발선에서 i번째로 도착하는지 체크해주면 된다.

public static boolean Check () {
    for (int i=1; i<N+1; i++) {
        int nx = i;
        int height = 1;
            
        while (height <= H) {
            if (map[height][nx] == 1) nx++;
            else if (map[height][nx] == 2) nx--;
                
            height++;
        }
            
        if (nx != i) return false;
    }
        
        
    return true;
}

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, H, limit;
    static int[][] map;
    static boolean isBreak = false;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); // 세로선 개수
        int 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] = 1;   // 오른쪽
            map[x][y+1] = 2; // 왼쪽
        }
        
        for (int i=0; i<4; i++) {
            limit = i;
            dfs(0);
            
            if (isBreak) break;
        }
        
        System.out.println(isBreak ? limit : -1);
    }
    
    public static void dfs(int cnt) {
        if (isBreak) return;
        
        if (limit == cnt) {
            if (Check()) {
                isBreak = true;
            }
            
            return;
        }
        
        for (int i=1; i<H+1; i++) {
            for (int j=1; j<N; j++) {
                if (map[i][j] == 0 && map[i][j+1] == 0) {
                    
                    // 백트래킹
                    map[i][j] = 1;
                    map[i][j+1] = 2;
                    
                    dfs(cnt+1);
                    
                    map[i][j] = 0;
                    map[i][j+1] = 0;
                }
            }
        }
    }
    
    public static boolean Check () {
        for (int i=1; i<N+1; i++) {
            int nx = i;
            int height = 1;
            
            while (height <= H) {
                if (map[height][nx] == 1) nx++;
                else if (map[height][nx] == 2) nx--;
                
                height++;
            }
            
            if (nx != i) return false;
        }
        
        
        return true;
    }
}