[BOJ] 15684번 사다리 조작 Java 풀이

 

DFS로 구현하다가 막혀, 다른 분의 풀이 소스를 참고했다. DFS 백트래킹으로 최솟값을 찾는 문제를 접근하면 반드시 끝까지 탐색하면서 최솟값을 갱신할 수 있으면 갱신하는 방식으로만 풀이가 가능하다고 생각했다. 그런데 모든 문제에 적용할 수는 없겠지만, 이 문제에서는 DFS를 약간 변형하는 방법으로 효율적으로 풀이를 하는 방법이 있었다.

 

참고: https://leveloper.tistory.com/96

 

 

 

풀이 구성

• void dfs(int x, int count): 가로선을 놓은 개수(count), 가로선을 놓을 지 말지 탐색할 높이(x)를 기준으로 재귀적으로 가로선을 놓고 다음 함수를 호출한 뒤, 다시 가로선을 제거하는 메서드

 

• boolean check(): 모든 세로선이 주어진 조건을 만족하는지 판별해주는 boolean 반환 메서드

 

• int[][] map: 사다리 정보 가진 2차원 배열, 1이면 오른쪽 방향 사다리를 둔 상태이고 2이면 왼쪽 방향으로 사다리를 둔 상태로 저장

 

• boolean finish: 현재 map을 기반으로 주어진 조건 만족하는지를 나타내는 플래그 변수

 

 

 

전체 코드

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.util.StringTokenizer; 
public class Main { 
	private static int n, m, h, answer; 
	private static int[][] map; 
	private static boolean finish = false; 
	
	public static void main(String[] args) throws Exception {
		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 + 1][n + 1]; 
		
		for (int i = 0; i < m; i++) { 
			int x, y;
			st = new StringTokenizer(br.readLine()); 
			x = Integer.parseInt(st.nextToken()); 
			y = Integer.parseInt(st.nextToken());
			// 1이면 오른쪽 방향 사다리, 2이면 왼쪽 방향 사다리
			map[x][y] = 1; 
			map[x][y + 1] = 2;
		} 
		
		// 사다리를 놓아보고 성공한다면 바로 break, 안되면 3번까지
		for (int i = 0; i <= 3; i++) { 
			answer = i; 
			dfs(1, 0); 
			if (finish) break;
		} 
		
		System.out.println((finish) ? answer : -1);
	} 
	
	private static void dfs(int x, int count) {
		// 답을 찾았다면 더이상 연산하지 않음
		if (finish) return; 
		
		// 0 ~ 3번째 사다리를 놓은 상태에서
		if (answer == count) { 
			// 모든 세로선이 조건을 만족한다면 종료
			if (check()) finish = true; 
			return;
		} 
		// 높이 depth를 1부터 h까지
		for (int i = x; i < h + 1; i++) {
			// 1번부터 마지막 전 세로선까지
			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 호출
					dfs(i, count + 1); 
					// 다시 가로선 제거
					map[i][j] = map[i][j + 1] = 0;
				}
			}
		} 
	} 
	
	// 모든 세로선이 조건을 만족하는지 판별해주는 boolean 반환 메서드 
	private static boolean check() { 
		// i: 세로선
		// y: 움직이는 위치에서의 column
		for (int i = 1; i <= n; i++) { 
			int x = 1, y = i;
			// j: 높이
			// x: h번 하강하는 과정에서의 depth
			for (int j = 0; j < h; j++) {
				// 1이면 오른쪽 이동
				if (map[x][y] == 1) y++;
				// 2이면 왼쪽 이동
				else if (map[x][y] == 2) y--;
				// 1만큼 내려감
				x++; 
			} 
			// 출발 세로선 인덱스와 도착한 세로선 인덱스가 다르면 false
			if (y != i) return false; 
		} 
		// 모든 세로선의 출발 세로선 인덱스와 도착한 세로선 인덱스가 같은 경우 true
		return true; 
	} 
}