백준 15684. 사다리조작 :: 돼지개발자

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

"브루트포스"

기존에 있는 사다리에 가능한 가로축을 모두 탐색해보는 브루트 포스 문제이다.

그럼 사다리를 배열에 어떻게 표현할까? 풀이에서 배열에 1로 체크된 값은 해당 위치에서 오른쪽으로 사다리가 존재한다고 생각하는 것이다. 따라서 인접한 열에 1 이 있지 않도록 가능한 모든 경우를 체크한다.

이렇게 생각하고 실제 탐색할때는 내 위치와 내 왼쪽 위치를 탐색한다.

1. 내 위치에 1이 있다. 오른쪽 사다리로 가라.

2. 내 왼쪽에 1이 있다. 왼쪽 사다리로 가라

위와같이 경우의 수를 만들고 실제로 사다리를 타봐서 체크한다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int N,M,H;
    static int[][] map;
    static boolean[][] visited;
    static int max;
    static boolean ok;
    
    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());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        
        map = new int[H+2][N+1];
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
        }
        
        for (int i = 0; i <= 3; i++) {
            max = i;
            solve(1,1,0);
            if(ok) break;
        }
        
        System.out.println(ok? max : -1);
    }
    
    static void solve(int x, int y, int cnt) {
        if(ok) return ;
        
        if(max == cnt) {
            if(check()) {
                ok = true;
            }
            return ;
        }
        
        for (int i = (y < N ? x : x+1); i <= H; i++) {
            for (int j = 1; j < N; j++) {
                if(map[i][j] == 1 || map[i][j-1] == 1 || map[i][j+1] == 1) continue;
                map[i][j] = 1;
                solve(i,j,cnt+1);
                map[i][j] = 0;
            }
        }
        
    }
    
    static boolean check() {
        for (int j = 1; j <= N; j++) {
            int i = 1;
            int temp = j;
            while( i <= H+1) {
                
                if(map[i][temp] == 1) {
                    temp++;
                }
                else if(map[i][temp-1] == 1) {
                    temp--;
                }
                i++;
            }
            if(j != temp) {
                return false;
            }
        }
        return true;
    }
    
}