https://www.acmicpc.net/problem/2784
풀이
3*3 배열 선언
가로 : 순열(재귀)로 row = 0,1,2인 곳을 길이 3 단어로 3번 채워넣음
세로 : 이후 col = 0,1,2로 새로운 단어를 만들어서, 기존 입력에 존재하고 가로를 채우는데 사용되지 않았으면 cnt++;
cnt == 3이면 가로,세로 어느곳을 읽어도 기존 입력에 존재하는 단어이며, 6개의 단어가 전부 사용되었음을 의미 << 답
정렬을 할 필요 없는 이유 :
입력이 사전 순으로 정렬되어있고, 순열 또한 순서대로 구성
최초 정답 발견 시 이미 사전 순으로 가장 앞선 상태
import static java.lang.System.exit;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
static String[] strings = new String[9];
static boolean[] used = new boolean[9];
static char[][] square = new char[3][3];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 6; i++) {
strings[i] = br.readLine();
}
solve(0);
System.out.println(0);
}
static void solve(int r) {
if (r == 3) {
if (isAns()) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(square[i][j]);
}
sb.append("\n");
}
System.out.println(sb.toString());
exit(0);
}
return;
}
for (int i = 0; i < 6; i++) {
String s = strings[i];
if (!used[i]) {
used[i] = true;
for (int c = 0; c < 3; c++) {
square[r][c] = s.charAt(c);
}
solve(r + 1);
used[i] = false;
for (int c = 0; c < 3; c++) {
square[r][c] = 0;
}
}
}
}
static boolean isAns() {
int cnt = 0;
boolean[] comp = new boolean[6];
for (int i = 0; i < 6; i++) {
comp[i] = used[i];
}
for (int c = 0; c < 3; c++) {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < 3; r++) {
sb.append(square[r][c]);
}
for (int i = 0; i < 6; i++) {
if (!comp[i] && strings[i].equals(sb.toString())) {
comp[i] = true;
cnt++;
break;
}
}
}
return cnt == 3;
}
}
'[백준] PS > Java [실랜디]' 카테고리의 다른 글
[백준 2002] 추월 - JAVA (0) | 2025.04.25 |
---|---|
[백준 2210] 숫자판 점프 - JAVA (0) | 2025.04.25 |
[백준 2371] 파일 구별하기 - JAVA (0) | 2025.04.25 |
[백준 3186] 소변기 - JAVA (1) | 2025.04.22 |
[백준 3182] 한동이는 공부가 하기 싫어! - JAVA (0) | 2025.03.30 |