(JAVA) 백준 3967번 : 매직 스타

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

3967번: 매직 스타

 

백트래킹 문제이다.

 

 

풀고 나서 제출 내역들을 보니

 

내가 속도가 다른 사람들에 비해 많이 느리게 나왔다.

 

하지만

 

다른 사람들의 풀이를 보는 것 보다

 

함수를 나눠 설계했기 때문에

 

이해는 쉬울 수 있을 것이다...!!!!

 

 

매커니즘

---

 

우선, 문제를 살펴보면

 

저 빨간 동그라미 부분에 들어갈 알파벳을 구하는 문제이다.

총 12칸이며, 5개 라인의 입력을 통해 초기 설정된 칸과 알파벳을 알 수 있다.

 

 

또한, 세 가지 조건을 충족해야 한다.

 

 1) 각 칸은 중복된 알파벳이 없다.

 2) A부터 L까지 1 ~ 12로 정의한다.

 3) 한 줄에 존재하는 4칸의 알파벳을 더하면 26이 되고, 총 6줄 전부 만족해야 한다.

 

 

 

다음,

 

아이패드로 작성해서 조금 읽기 난해할 수 있다..

 

 

나는 전체 길이가 13인(인덱스 1 ~ 12 사용) 배열을 총 3개를 만들었다.

*** 참고로, 알파벳은 'A' == 65 아스키코드를 참고하여 index = '해당 알파벳' - 64 로 계산해서 진행했다.

ex) A : 65 - 64 = 1(첫 번째는 1이라고 정했으므로 만족)

ex2) B : 66 - 64 = 2

 

1) boolean 배열. 해당 알파벳이 이전 줄 또는 이전 칸에서 사용했는지 여부를 파악하는 배열.

 

2) int 배열 2개.

  2-1) 첫 번째 int 배열은 해당 번째 칸에 들어가는 알파벳(번째) 값이 들어간다.

  2-2) 두 번째 int 배열은 사전순으로 가장 작은 알파벳들을 담는 배열이다. 

 

 

마지막으로,

 

각 줄마다 4개의 칸을 더하면 26이 되는 조건을 판별하기 위해

각 줄에 들어가있는 칸의 인덱스를 별도의 2차원 배열에 담았다. 

 

이를 가지고 위의 int 배열의 인덱스 값만 찾아 더해 계산하면 된다.

 

 

 

 

매커니즘의 단계로 넘어가보자.

 

 

매커니즘

---

 

1. x 또는 . 이 아닌 문자가 들어오면 무조건 초기 알파벳에 해당하므로, 알파벳 - 64 한 값을 int 배열에 넣고, boolean 배열의 인덱스 값을 찾아 true로 변경한다. (해당 알파벳을 사용했기 때문에)

 

 

2. 첫 번째 칸을 파라미터로 하는 백트래킹 함수를 호출한다.

 

 

2-1. 해당 칸에 이미 초기 알파벳이 들어가있으면 다음 칸을 파라미터로 하는 백트래킹 함수 호출

 

2-2. 알파벳 A ~ L(1 ~ 12)를 하나씩 사용해보는 For문을 사용해 아직 사용하지 않은 알파벳을 찾는다.

2-2-2.  찾은 알파벳을 넣은 경우와 넣지 않은 경우를 백트래킹 함수로 표현한다.

 

 

3. 모든 칸에 알파벳을 채우면 모든 줄이 26을 만족하는지 판별한다.

 

 

4. 만족하는 경우 정답

4-1. 만족하지 않으면 다음 경우를 찾으러 돌아간다.

 

 

말은 쉬워보이는데

코드가 길어질 수 밖에 없습니다...

 

저는 함수로 기능을 분리하고

흐름을 파악하기 좀 더 수월하게 작성했기 때문이죠..

 

 

 

이상입니다.

 

 

감사합니다!

 

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// 매직 스타
	// 백트래킹
	public class p3967 {
	static boolean[] usedAlphabet; // 해당 알파벳을 사용했는지 파악하는 boolean 배열
	static int[] alphabet; // 맨 첫번째 줄부터 순서대로 어느 알파벳이 사용되었는지 파악하는 int 배열. 0 : A, 11 : L
	static int[] result;
	static int[][] magicLine = {
	{1, 3, 6, 8},
	{2, 3, 4, 5},
	{2, 6, 9, 12},
	{8, 9, 10, 11},
	{5, 7, 10, 12},
	{1, 4, 7, 11}
	};
	static int MAX_LENGTH = 13;
	static int ASCII = 64;
	static boolean checked = false;
	static StringBuilder sb = new StringBuilder();
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	usedAlphabet = new boolean[MAX_LENGTH];
	alphabet = new int[MAX_LENGTH];
	result = new int[MAX_LENGTH];
	// 입력 값 탐색
	int index = 1;
	for(int i = 0; i < 5; i++) {
	String line = br.readLine();
	for(int j = 0; j < line.length(); j++) {
	char ch = line.charAt(j);
	if(ch == 'x') {
	index++;
	}
	else {
	if(ch != '.') {
	alphabet[index] = ch - ASCII;
	usedAlphabet[ch - ASCII] = true; // A는 아스키코드 65. 인덱스가 1 ~ 12이므로 64를 뺌.
	index++;
	}
	}
	}
	}
	backTracking(1);
	getMagicStar();
	}
	private static void backTracking(int index) {
	if(checked) {
	return;
	}
	if(index == MAX_LENGTH) {
	if(isAbleMagicStar()) {
	for(int i = 1; i < MAX_LENGTH; i++) {
	result[i] = alphabet[i];
	}
	checked = true;
	}
	return;
	}
	// 입력 값에서 이미 확정되어 있는 경우
	if(alphabet[index] != 0) {
	backTracking(index + 1);
	}
	else {
	// usedAlphabet 탐색하는 반복문
	for(int i = 1; i < MAX_LENGTH; i++) {
	// 이미 사용한 숫자인 경우
	if(usedAlphabet[i]) {
	continue;
	}
	// 선택한 경우
	alphabet[index] = i;
	usedAlphabet[i] = true;
	backTracking(index + 1);
	// 선택하지 않은 경우
	alphabet[index] = 0;
	usedAlphabet[i] = false;
	}
	}
	}
	private static boolean isAbleMagicStar() {
	for(int i = 0; i < magicLine.length; i++) {
	int sum = 0;
	for(int j = 0; j < magicLine[0].length; j++) {
	sum += alphabet[magicLine[i][j]];
	}
	if(sum != 26) {
	return false;
	}
	}
	return true;
	}
	private static void getMagicStar() {
	int index = 1;
	for(int line = 0; line < 5; line++) {
	switch(line) {
	case 0: case 4:
	for(int i = 0; i < 9; i++) {
	if(i == 4) {
	System.out.print((char) (result[index++] + ASCII));
	}
	else {
	System.out.print(".");
	}
	}
	break;
	case 1: case 3:
	for(int i = 0; i < 9; i++) {
	if(i % 2 == 1) {
	System.out.print((char) (result[index++] + ASCII));
	}
	else {
	System.out.print(".");
	}
	}
	break;
	case 2:
	for(int i = 0; i < 9; i++) {
	if(i == 2 || i == 6) {
	System.out.print((char) (result[index++] + ASCII));
	}
	else {
	System.out.print(".");
	}
	}
	break;
	}
	System.out.println();
	}
	}
	}

view raw p3967.java hosted with ❤ by GitHub