[백준] PS/Java [실랜디]

[백준 2784] 가로 세로 퍼즐 - JAVA

SH3542 2025. 4. 25. 19:02

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;
  }
}