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

1.  문제 링크

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

2.  문제

요약

• 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있습니다.
• 인접한 세로선 사이에는 가로 선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖습니다.
• 가로선은 인접한 두 세로선을 연결해야 하는데, 두 가로선이 연속하거나 서로 접하면 안 됩니다.
• 사다리에 가로선을 추가해서 i번 세로선의 결과가 i번이 나오게 하도록 하려고 합니다.
• 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 10보다 작거나 같은 세로선의 개수 N, 0보다 크거나 같고 (N - 1) * H보다 작거나 같은 가로선의 개수 M, 1보다 크거나 같고 30보다 작거나 같은 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어지고 두 번째 줄부터 M개의 줄에는 가로선의 장보가 한 줄에 하나씩 주어집니다. 가로선의 정보는 1보다 크거나 같고 H보다 작거나 같은 정수 a와 1보다 크거나 같고 N - 1보다 작거나 같은 정수 b로 나타내는데, 이는 b번 세로선과 b + 1번 세로선을 a번 점선 위치에서 연결했다는 의미입니다.
  • 가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가합니다.
  • 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가합니다.
  • 입력으로 주어지는 가로선이 서로 연속하는 경우는 없습니다.
• 출력: 첫 번째 줄에 i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력합니다. 만약 정답이 3보다 크다면 -1을 출력하고, 불가능한 경우에도 -1을 출력합니다.

3.  소스코드

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

public class Main {
	static int N, M, H, min;
	static boolean[][][] horizontalLine;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		H = scanner.nextInt();
		horizontalLine = new boolean[N + 1][H][2];
		for(int count = 0; count < M; count++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			horizontalLine[b][a - 1][0] = true;
			horizontalLine[b + 1][a - 1][1] = true;
		}
	}
	
	static void solution() {
		if(isRight()) {
			System.out.println(0);
			return;
		}
		min = Integer.MAX_VALUE;
		rec_func(1, 0);
		min = (min == Integer.MAX_VALUE) ? -1 : min;
		System.out.println(min);
	}
	
	static void rec_func(int idx, int depth) {
		if(depth > 3) return;
		if(depth <= 3) {
			if(isRight()) {
				min = Math.min(min, depth);
				return;
			}
		}
		for(int index = idx; index < N; index++) {
			for(int col = 0; col < H; col++) {
				if(!horizontalLine[index][col][0] && !horizontalLine[index + 1][col][0]) {
					horizontalLine[index][col][0] = true;
					horizontalLine[index + 1][col][1] = true;
					rec_func(index, depth + 1);
					horizontalLine[index][col][0] = false;
					horizontalLine[index + 1][col][1] = false;
				}
			}
		}
	}
	
	static boolean isRight() {
		for(int index = 1; index <= N; index++) {
			int destination = index;
			for(int col = 0; col < H; col++) {
				if(horizontalLine[destination][col][0]) destination += 1;
				else if(horizontalLine[destination][col][1]) destination -= 1;
			}
			if(destination != index) return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 주어진 단어를 word라는 배열에 담고 word_type이라는 배열에 word의 각 문자가 어떤 유형인지 넣습니다. 유형은 자음 또는 모음은 연속해서 3번 나오면 안되고 L은 반드시 포함해야 하며 밑줄 자리에 알파벳을 채워야 하기 때문에 자음, 모음, L, 밑줄로 나눕니다.
  • 밑줄: 0, 모음: 1, 자음: 2, L: 3

public long findCase(int idx, int vowelNum, int consonantNum, int flag) {
		if(vowelNum >= 3 || consonantNum >= 3) {
			return 0;
		}
		if(idx == word.length) {
			return flag;
		}
		long result = 0;
		if(word_type[idx] == 0) {
			result += findCase(idx + 1, 0, consonantNum + 1, flag) * 20;
			result += findCase(idx + 1, vowelNum + 1, 0, flag) * 5;
			result += findCase(idx + 1, 0, consonantNum + 1, 1);
		} else {
			if(word_type[idx] == 1) {
				result += findCase(idx + 1, vowelNum + 1, 0, flag);
			} else {
				if(word_type[idx] == 3) {
					result += findCase(idx + 1, 0, consonantNum + 1, 1);
				} else {
					result += findCase(idx + 1, 0, consonantNum + 1, flag);
				}
			}
		}
		return result;
	}

• findCase 함수에서는 idx, vowelNum, consonantNum, flag라는 인자를 받는데, idx는 주어진 단어에서 현재 위치를 뜻하고 vowelNum과 consonantNum은 각각 연속된 모음의 개수와 연속된 자음의 개수를 뜻하며 flag는 L이 단어에 포함되었는지 여부를 뜻합니다. 만약 L이 없다면 0을, L이 있다면 1을 나타냅니다.
• 만약 vowelNum이나 consonantNum이 3보다 크거나 같다면 자음 또는 모음이 연속적으로 3번 나오면 안된다는 조건에 어긋나므로 해당 호출에서는 0을 반환합니다.
• 만약 idx가 주어진 단어의 길이와 같다면 단어의 마지막까지 밑줄에 단어를 채웠다는 뜻이므로 개수를 계산할 때 이용하기 위해 flag를 반환합니다.
• 밑줄을 알파벳으로 바꿔 즐거운 단어를 만들 수 있는 경우의 수를 나타내는 변수인 result를 생성하고 값을 0으로 초기화합니다.
• 만약 현재 위치의 문자 유형이 밑줄이라면 자음을 채우는 경우, 모음을 채우는 경우, L로 채우는 경우를 각각 재귀함수를 이용하여 마지막 문자까지 진행합니다. 이 때, 전달하는 인자는 다음과 같습니다.
  1. 자음을 채우는 경우
     • (idx + 1, 0, consonantNum + 1, flag)
       • 자음으로 채운다면 더이상 모음이 연속되지 않기 때문에 모음의 개수는 0으로 만듭니다.
  2. 모음을 채우는 경우
     • (idx + 1, vowelNum + 1, 0, flag)
       • 모음으로 채운다면 더이상 자음이 연속되지 않기 때문에 자음의 개수는 0으로 만듭니다.
  3. L을 채우는 경우
     • (idx + 1, 0, consonantNum + 1, 1)
       • L로 채운다면 L 또한 자음이기 때문에 더이상 모음이 연속되지 않기 때문에 모음의 개수는 0으로 만들고 L이 단어에서 채워졌기 때문에 flag는 무조건 1을 넘겨줍니다.
• 위와 같이 인자를 전달하는데 자음은 L을 제외하고 20개가 존재하기 때문에 호출된 재귀함수에서 반환된 것에 20을 곱해서 result에 더해주고 모음은 5개가 존재하기 때문에 호출된 재귀함수에서 반환된 것에 5를 곱해서 result에 더해줍니다.
• 만약 현재 위치의 문자 유형이 모음이라면 더이상 자음이 연속되지 않기 때문에 연속된 자음의 개수는 0으로 만들고 연속된 모음의 개수에 1을 더해준 후에 재귀함수 호출을 통해 다른 문자들을 확인합니다.
• 만약 현재 위치의 문자 유형이 자음이라면 더이상 모음이 연속되지 않기 때문에 연속된 모음의 개수는 0으로 만들고 연속된 자음의 개수에 1을 더해준 후에 재귀함수 호출을 통해 다른 문자들을 확인합니다.
• 만약 현재 위치의 문자 유형이 L이라면 더이상 모음이 연속되지 않기 때문에 연속된 모음의 개수는 0으로 만들고 연속된 자음의 개수에 1을 더해주며 L이 단어에 포함되므로 flag를 1로 만든 후에 재귀함수 호출을 통해 다른 문자들을 확인합니다.
• 모든 재귀함수 호출이 끝났을 때의 result 값이 밑줄을 알파벳으로 바꿔 즐거운 단어를 만들 수 있는 경우의 수가 되므로 해당 값을 출력합니다.