BOJ - 사다리 조작

15684 사다리 조작 : https://www.acmicpc.net/problem/15684

---

Problem

---

Solve

문제 풀이는 아래와 같다.

1. int[][] map = new int[H+1][N+1] 로 초기화한 후. M개의 조건에서 map[a][b] = 1, map[a][b+1] = 2로 갱신한다.
   • 가로선은 연속해서 설치할 수 없기 때문에 b+1에 2로 이동할 방향을 표시할 수 있다.
   • map[a][b] = 1일 경우 b에서 b+1로 이동
   • map[a][b] = 2일 경우 b에서 b-1로 이동
   • map[a][b] = 0일 경우 b에서 b로 이동
2. 추가하는 가로선의 개수의 최솟값을 출력해야하기 때문에 추가할 사다리 개수를 0~3개로 정의한다음 백트래킹을 돌면서 사다리를 모든 경우의 위치에 추가한다.
3. 추가한 사다리 개수가 정의한 추가 사다리 개수를 만족한다면 각 세로선에서 출발하여 map[i][j] 값 여부에 따라 왼쪽,오른쪽으로 이동한다. i == H+1에 도착하였을 때 출발한 j에서 도착한 j와 비교하여 모든 세로선에서의 조건이 같다면 반복을 종료하고 해당 사다리 개수를 반환한다.
4. 만약 모든 경우의 사다리를 설치해보아도 조건을 만족하지 못한다면 -1을 반환한다.

---

Code

public class 사다리조작 {
	static int N;
	static int M;
	static int H;
	static int[][] map;
	static int answer;
	static boolean finish = false;
	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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			//a번 세로에 b번 세로선과 b+1번 세로선을 연결하는 가로선.
            //1 : b에서 b+1로 이동
            //2 : b에서 b-1로 이동
			map[a][b] = 1;
			map[a][b+1] = 2;
		}

		answer = 0;
		for(int i=0;i<=3;i++){
        	//추가할 사다리 개수 정의
			answer = i;
			dfs(1, 0);
			if(finish) break;
		}

		if(!finish) answer = -1;

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//각 세로선에서 출발 했을 때 동일한 위치에 도착하는지 확인
	static boolean check(){
		for(int i=1;i<=N;i++){
			int x = i;
			for(int y=1;y<=H;y++){
				if(map[y][x] == 1) x++;
				else if(map[y][x]==2) x--;
			}
			if(i != x) return false;
		}
		return true;
	}
    //사다리 추가
	static void dfs(int y, int count){
		if(finish) return;
        //추가할 사다리 개수 정의와 동일하게 사다리를 추가했다면 각 세로선을 출발했을때의 조건을 만족하는지 확인
        //만족한다면 finish = true로 하여 반복을 종료시킨다.
		if(count == answer){
			if(check()){
				finish = true;
			}
			return;
		}

		//현재 y축보다 이전의 y축에는 사다리를 설치할 필요가 없다.
		for(int i=y;i<=H;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(i,count+1);
					map[i][j] = map[i][j+1] = 0;
				}
			}
		}
	}
}

---

Result

---

Reference