백준 3967 매직 스타(DFS)

3967번: 매직 스타

문제는 어렵지 않았지만 시간초과에 대해서 많이 고전한 문제다.

단순히 빈칸에 대해서 사용할 수 있는 알파벳을 하나씩 넣어보고(완전탐색) 합이 26이 되면 종료하는 문제

 

근데 여기서 문제는 완전탐색을 해버리겠다고 한다면 빈칸에 대해서 넣어볼 수 있는 알파벳 여러개를 한번씩 모두 넣어본다는 것(순열)인데 이 문제는 그런 모든 경우를 구하는 문제가 아니다.

 

아래 코드에 보면 DFS의 재귀부분에 break;를 넣었는데 이 부분이 매우 핵심적인 부분이다.

 

문제에서 사전순으로 나올 수 있는 정답 하나를 바로 출력하는 것이기 때문에 빈칸 x에 대해서 알파벳을 하나 넣었으면 그 자리에 대해서 더이상 고려를 해줄 필요가 없다.

 

이 부분을 break 안해주고 계속 for를 반복해서 하나씩 넣어보는 행위(순열)을 한다면 무조껀 시간초과!

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


public class Main_3967 {
	static int[][] line_idx_list = {
			{2,3,4,5},{5,7,10,12},{2,6,9,12},{8,9,10,11},{1,3,6,8},{1,4,7,11}
	};
	static boolean[] visited = new boolean[12];
	static boolean checked = false;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] data = new int[12];

		int idx = 0;
		
		for (int i = 0; i < 5; i++) {
			String input = br.readLine();
			for (int j = 0; j < 9; j++) {
				if (input.charAt(j) != '.') {
					if (input.charAt(j) == 'x') {
						data[idx++] = -1;
					}
					else {
						data[idx++] = input.charAt(j) - 'A';
						visited[input.charAt(j) - 'A'] = true;
					}
				}
			}
		}


		dfs(data);
		
	}
	

	public static void dfs(int[] data) {

		if (end_check(data)) {
			if (line_check(data)) {
				draw(data);
				System.exit(0);
				}

			return; 
		}

		//순열을 만드는 코드라고 생각함
		//하지만 문제는 순열처럼 순서를 요구하는게 아닌 단순히 사전적으로 나오게 하는것이 목적
		for(int i = 0; i < 12; i++) {
			if(visited[i]) 
				continue;		
			for (int j = 0; j < 12; j++) {
				if (data[j] == -1) {
					data[j] = i;
					visited[i] = true;
					dfs(data);
					data[j] = -1;
					visited[i] = false;
					break; //따라서 순열을 만들지말고 그 자리에 값을 넣었으면 그 자리에 대한 재귀는 바로 끝내버리기
				}
			}

			
		}
	}
	
	public static boolean end_check(int[] data) {
		for (int i = 0; i < 12; i++) {
			if (data[i] == -1)
				return false;
		}
		return true;
	}
	
	public static boolean line_check(int[] data) {
		for (int i = 0; i < 6; i++) {
			int sum = 0;
			for (int j = 0; j < 4; j++) {
				sum += data[line_idx_list[i][j]-1];
			}
			if (sum != 22) //26-4
				return false;
		}
		return true;
	}
	
	private static void draw(int[] data) {
		int index = 0;
		for(int line = 0; line < 5; line++) {
			if (line == 0 || line == 4) {
				for(int i = 0; i < 9; i++) {
					if(i == 4) {
						System.out.print((char) (data[index++] + 65));
					}
					else {
						System.out.print(".");
					}
				}
			}
			else if(line == 1 || line ==3) {
				for(int i = 0; i < 9; i++) {
					if(i % 2 == 1) {
						System.out.print((char) (data[index++] + 65));
					}
					else {
						System.out.print(".");
					}
				}
			}
			else if(line == 2) {
				for(int i = 0; i < 9; i++) {
					if(i == 2 || i == 6) {
						System.out.print((char) (data[index++] + 65));
					}
					else {
						System.out.print(".");
					}
				}
			}
			System.out.println();
		}
	}

}