[백준] 2784. 가로 세로 퍼즐 - 실버3

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

2784번: 가로 세로 퍼즐

 

문제 요약

6개의 단어가 주어졌을 때, 이를 가지고 가로 세로 퍼즐을 만드는 프로그램을 작성하시오. 단어 3개는 가로줄, 3개는 세로줄로 배치해야한다.

6개 단어를 3*3 가로 세로 퍼즐에 놓을 수 없다면 0을 출력한다. 그렇지 않다면, 3개 줄에 퍼즐을 출력한다. 만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다. 사전순으로 비교를 할 때는, 모두 한 줄로 이어붙인 9개의 단어를 생각하면 된다.

 

문제 해결 아이디어

정답이 되는 가로 세로 퍼즐을 2차원 배열로 생각하지 않고 0행, 1행, 2행, 0열, 1열, 2열 순으로 붙어 있는 1차원 배열이라고 생각했다. 따라서 정답이 되는 result 배열은 String형 일차원 배열이다.

0행, 1행, 2행에 오는 단어 세 개를 뽑으면 자동으로 0열, 1열, 2열은 정해지는 것이므로 그게 정답이 되는지, 되지 않는지 체크해 주기로 했다.

i번째 열로 뽑힌 단어들을 해당하는 단어들의 i번째 알파벳과 하나하나 비교하면서 하나라도 틀리면 바로 return 하게 했고, 끝까지 이 과정을 통과하면 정답이 된다.

단어를 뽑는 과정 전에 Arrays.sort()를 수행하기 때문에 무조건 첫 번째 결과가 사전순으로 앞선다.

 

완성된 코드

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

public class Main_BOJ_2784_가로세로퍼즐 {
	/*
	 * 92ms
	 */
	static String[] input;
	static String[] result;
	static boolean[] isSelected;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 0행, 1행, 2행, 0열, 1열, 2열
		input = new String[6];
		for (int i = 0; i < 6; i++) {
			input[i] = br.readLine();
		}
		result = new String[6];
		isSelected = new boolean[6];
		Arrays.sort(input);
		pick(0);
		System.out.println("0");
	}

	public static void pick(int cnt) {
		
		if (cnt == 6) {
			char[] row, col;
			for (int i = 0; i < 3; i++) {
				col = result[i+3].toCharArray();
				for (int j = 0; j < 3; j++) {
					row = result[j].toCharArray();
					if (row[i] != col[j])
						return;
				}
			}
			
			for (int i = 0; i < 3; i++) {
				System.out.println(result[i]);
			}
			System.exit(0);
		}
		
		for (int i = 0; i < 6; i++) {
			if (isSelected[i])
				continue;
			isSelected[i] = true;
			result[cnt] = input[i];
			pick(cnt + 1);
			isSelected[i] = false;
		}
	}
}