[BOJ 15684] 사다리 조작 (Java)

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

15684번: 사다리 조작

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_BOJ_15684 {
	static int N, M, H;
	static int[][] ladder;
	static int answer=-1;
	static ArrayList<int[]> pos=new ArrayList<>();
	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());
		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;
		}
		for (int i=1; i<=H; i++) {
			for (int j=1; j<N; j++) {
				pos.add(new int[] {i,j});
			}
		}
		for (int i=0; i<=3; i++) {
			if (backtracking(0, 0, i)) {
				answer=i;
				break;
			}
		}
		System.out.println(answer);

	}
	private static boolean backtracking(int start, int cnt, int target) {
		int r, c;
		if (cnt==target) {
			if (play()) return true;
			else return false;
		}
		for (int i=start; i<pos.size(); i++) {
			r=pos.get(i)[0];
			c=pos.get(i)[1];
			if (isValid(r,c)) {
				ladder[r][c]=1;
				if (backtracking(start+1, cnt+1, target)) return true;
				ladder[r][c]=0;
			}
		}		
		return false;
	}
	
	private static boolean isValid(int r, int c) { 		//사다리 설치 X && 접하지 않은 곳 
		if (ladder[r][c]==1) return false;
		if (c-1>=1 && ladder[r][c-1]==1) return false;
		if (c+1<=N-1 && ladder[r][c+1]==1) return false;
		return true;
	}
	
	
	private static boolean play() {
		int r, c;
		for (int i=1; i<=N; i++) {
			r=1;
			c=i;
			while (r<=H) {
				if (c-1>=1 && ladder[r][c-1]==1) c-=1;
				else if (ladder[r][c]==1) c+=1;
				r+=1;
			}
			if (c!=i) return false;				
		}
/*		for (int i=1; i<=H; i++) {
			for (int j=1; j<=N; j++) {
				System.out.print(ladder[i][j]);
			}
			System.out.println();
		}*/
		return true;
	}

}

더 깔끔하게 풀 수 있었다..

 

0개부터~3개까지 조작할 사다리 갯수를 완탐한다

이때 성공 case가 나오면 그 갯수를 리턴하면 된다

 

조작할 사다리를 구할 때, 나처럼 어렵게 arraylist 를 사용할 필요 없이 2중 for문을 돌려서 사다리 갯수를 선택해 주면 된다. 

그리고 isValid 함수에서, if (ladder[i][j] == 0 && ladder[i][j - 1] == 0 && ladder[i][j + 1] == 0) 이런 식으로 체크해줘도 OK 다. 어차피 배열 자체는 실제 사용하는 크기에 비해 크기 때문에 이렇게 해도 arrayoutofboundexception 이 나지 않는다.