[백준 15684, Java] 사다리 조작

문제

www.acmicpc.net/problem/15684

15684번: 사다리 조작

풀이

 

문제를 두 부분으로 나눌 수 있다. 사다리를 놓는다 -> i번 세로선의 결과가 i번이 나오는지 확인한다 이다. 

 

먼저 사다리를 놓는 경우를 보자. 사다리는 최소 0개 부터 최대 3개까지 놓을 수 있다. 그 중 조건을 만족하는 최소값을 구하는 거다. 위의 문제는 NM과 K(1)과 비슷하다. 현재까지 뽑은 사다리의 갯수와 최솟값을 비교하는 거다. 만약 현재까지 뽑은 사다리의 갯수가 최솟값이상이면 더이상 뽑을 필요가 없다. 

 현재까지 뽑은 사다리의 갯수가 최솟값보다 작으면, 먼저 현재까지 뽑힌 사다리에 대해서 i번 세로선의 결과가 i번이 나오는지 확인한다. 결과가 나오지 않는 경우 사다리를 하나 더 뽑는다. 

 

public static void check(int count,int pickedR, int pickedC) {
	if(count>=minCount) {
		return;
	}
	else {
		if(isValid()){
			if(count<minCount) {
				minCount = count;
			}
			
		}
		else {
			for(int r = pickedR; r<=H; r++) {
				for(int c = (r==pickedR)? pickedC : 1; c<=N-1; c++) {
					if(!link[r][c] && !link[r][c-1] && !link[r][c+1]) {
						link[r][c] =true;
						
						check(count+1, r,c);
						link[r][c] = false;
					}
				}
			}
		}
	}
	
}

 

 이제 i번 세로선의 결과가 i번이 나오는지 확인 하는 코드를 생각해보자. 사다리를 좌표라고 생각하고 연결상태를 표현해야하는데, 연결은 양방향이므로 좌표에는 한방향에 대해서만 생각해줘야한다. 다시말해 (2,3)-(2,4)가 양방향으로 연결되어 있는데 2차원 배열로 나타내려면 양뱡향이 아닌 단방향에 대한 정보를 저장해야한다. 따라서 boolean link [r][c]를 (r,c)에서 (r,c+1)로 연결이 되어있는지 아닌지라고 한다.

 

 그러면 이제 이동하는 경우를 보자. 현재위치에서 왼쪽으로 연결되어있는지 확인 후 연결되어있으면 왼쪽으로, 아닌경우 오른쪽을 확인하여 연결되어있으면 오른쪽으로, 둘다 연결되어  있지 않으면 아래로 이동한다. 현재위치에서 왼쪽으로 연결되어 있는지를 확인하려면 link[r][c-1]의 값을 확인해야하고, 오른쪽으로 연결되어 있는지 확인하려면 link[r][c]의 값을 확인해야한다. 

 

 이때 c-1이 범위 안에 있는지, 밖에 있는지에 대한 코드를 줄이기 위해 link배열의 크기를 [H+2][N+2]로 초기화 했다. 

 

public static boolean isValid() {
	for(int node =1; node<=N; node++) {
		boolean[][] visited = new boolean[H+2][N+2];
		int r = 1;
		int c = node;
		visited[r][c] = true;
		
		while(r<=H) {
			//왼쪽으로 연결되어있는지 확인
			if(link[r][c-1] && !visited[r][c-1]) {
				c = c-1;
				
				visited[r][c] = true;
				continue;
			}
			//오른쪽으로 연결되어있는지 확인
			if(link[r][c] && !visited[r][c+1]) {
				c = c+1;
				
				visited[r][c] = true;
				continue;
			}
			
			//둘다 아니면 아래로 이동
			r = r+1;		
			visited[r][c] = true;
			
			
		}
		
		if(node!=c) {
			return false;
		}
	}
		return true;
}

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int H;
	static boolean[][] link;
	static boolean[][] picked;
	static int minCount = 4;
	
	public static void main(String[] args) throws Exception {
		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());
		
		link = new boolean[H+2][N+2];
		picked = new boolean[H+2][N+2];
		
		for(int m =1; m<=M; m++) {
			st = new StringTokenizer(br.readLine()," ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			link[r][c] = true;
		}

		
		check(0, 1,1);
		if(minCount ==4) {
			bw.write(String.valueOf(-1));
		}
		else {
			bw.write(String.valueOf(minCount));
		}
		bw.flush();
		
		
		
	}
	public static void check(int count,int pickedR, int pickedC) {
		if(count>=minCount) {
			return;
		}
		else {
			if(isValid()){
				if(count<minCount) {
					minCount = count;
				}
				
			}
			else {
				for(int r = pickedR; r<=H; r++) {
					for(int c = (r==pickedR)? pickedC : 1; c<=N-1; c++) {
						if(!link[r][c] && !link[r][c-1] && !link[r][c+1]) {
							link[r][c] =true;
							
							check(count+1, r,c);
							link[r][c] = false;
						}
					}
				}
			}
		}
		
	}
	public static boolean isValid() {
		for(int node =1; node<=N; node++) {
			boolean[][] visited = new boolean[H+2][N+2];

			int r = 1;
			int c = node;
			visited[r][c] = true;
			
			while(r<=H) {
				//왼쪽으로 연결되어있는지 확인
				if(link[r][c-1] && !visited[r][c-1]) {
					c = c-1;
					
					visited[r][c] = true;
					continue;
				}
				//오른쪽으로 연결되어있는지 확인
				if(link[r][c] && !visited[r][c+1]) {
					c = c+1;
					
					visited[r][c] = true;
					continue;
				}
				
				//둘다 아니면 아래로 이동
				r = r+1;		
				visited[r][c] = true;
				
				
			}
			
			if(node!=c) {
				return false;
			}
		}

		return true;
	}

}