[Java] 백준 3967번 매직스타

백트래킹 문제입니다.

각 직선의 합이 26이 나오는 경우를 만들어 출력해야합니다.
결과는 가능한 경우로 주어지며, 답이 여러 개일 경우 사전순으로 빠른 순으로 출력해야합니다.

각 직선은 총 6가지가 가능합니다.
숫자 12개의 크기를 가진 배열을 만들어주고, 순열을 통해서 값을 넣었습니다.
만든 후 가능한지 테스트하였습니다.
위의 과정을 반복해서 가능한 경우 출력해주고 종료해주었습니다.

import java.io.*;
import java.util.*;

public class Main {
  static boolean suc = false;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] arr = new int[13];
    int[] visit = new int[13];
    int cnt = 1;

    for (int i = 0; i < 5; ++i) {
      String s = br.readLine();
      for (int j = 0; j < 9; ++j) {
        if (s.charAt(j) == '.') {
          continue;
        } else if (s.charAt(j) == 'x') {
          arr[cnt] = 0;
          ++cnt;
        } else {
          arr[cnt] = (s.charAt(j) - 'A') + 1;
          visit[arr[cnt]] = 1;
          ++cnt;
        }
      }
    }

    dfs(arr, visit, 1);
  }

  public static void dfs(int[] arr, int[] visit, int index) {
    if (index == 13 | suc) {
      if (check(arr)) {
        print(arr);
        suc = true;
      }
      return;
    }

    if (arr[index] != 0) {
      dfs(arr, visit, index + 1);
      return;
    }

    for (int i = 0; i < 12; ++i) {
      if (visit[i + 1] == 1) {
        continue;
      }
      arr[index] = i + 1;
      visit[arr[index]] = 1;
      dfs(arr, visit, index + 1);
      visit[arr[index]] = 0;
      arr[index] = 0;
    }
  }

  public static boolean check(int[] arr) {
    if (arr[1] + arr[3] + arr[6] + arr[8] != 26) {
      return false;
    }
    if (arr[1] + arr[4] + arr[7] + arr[11] != 26) {
      return false;
    }
    if (arr[8] + arr[9] + arr[10] + arr[11] != 26) {
      return false;
    }
    if (arr[2] + arr[3] + arr[4] + arr[5] != 26) {
      return false;
    }
    if (arr[2] + arr[6] + arr[9] + arr[12] != 26) {
      return false;
    }
    if (arr[5] + arr[7] + arr[10] + arr[12] != 26) {
      return false;
    }
    return true;
  }

  public static void print(int[] arr) {
    for (int i = 0; i < 9; ++i) {
      if (i == 4) {
        System.out.print((char) (arr[1] + 'A' - 1));
      } else {
        System.out.print('.');
      }
    }
    System.out.println();

    for (int i = 0; i < 9; ++i) {
      if (i == 1) {
        System.out.print((char) (arr[2] + 'A' - 1));
      } else if (i == 3) {
        System.out.print((char) (arr[3] + 'A' - 1));
      } else if (i == 5) {
        System.out.print((char) (arr[4] + 'A' - 1));
      } else if (i == 7) {
        System.out.print((char) (arr[5] + 'A' - 1));
      } else {
        System.out.print('.');
      }
    }
    System.out.println();

    for (int i = 0; i < 9; ++i) {
      if (i == 2) {
        System.out.print((char) (arr[6] + 'A' - 1));
      } else if (i == 6) {
        System.out.print((char) (arr[7] + 'A' - 1));
      } else {
        System.out.print('.');
      }
    }
    System.out.println();

    for (int i = 0; i < 9; ++i) {
      if (i == 1) {
        System.out.print((char) (arr[8] + 'A' - 1));
      } else if (i == 3) {
        System.out.print((char) (arr[9] + 'A' - 1));
      } else if (i == 5) {
        System.out.print((char) (arr[10] + 'A' - 1));
      } else if (i == 7) {
        System.out.print((char) (arr[11] + 'A' - 1));
      } else {
        System.out.print('.');
      }
    }
    System.out.println();

    for (int i = 0; i < 9; ++i) {
      if (i == 4) {
        System.out.print((char) (arr[12] + 'A' - 1));
      } else {
        System.out.print('.');
      }
    }
    System.out.println();
  }
}