[Java] 백준 16432번 떡장수와 호랑이

N일 동안 전날과 다른 떡을 줄 수 있는지 찾는 문제입니다.

단순히 전날과 다른 떡을 주면 되므로 아래 두 경우는 같다고 볼 수있습니다.
1. 1 - 2 (1일에 1번떡, 2일에 2번떡)
2. 3 - 2 (1일에 3번떡, 2일에 2번떡)

DFS로 모든 경우의 수를 확인해주었습니다.
중복된 과정이 많이 생기므로 방문배열을 만들어서 X일에 A떡을 주었다는 것을 기록합니다.
동일하게 X일에 A떡을 준 경우 이미 탐색했으므로 탐색하지 않습니다.

최종적으로 N일 동안 다 주었을때 준 떡을 순서대로 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
  static int n;
  static int chk;
  static int[][] visit;
  static String result;
  static ArrayList<ArrayList<Integer>> al;
  static BufferedReader br;
  static BufferedWriter bw;

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

    n = Integer.parseInt(br.readLine());
    visit = new int[n][10];
    al = new ArrayList<>();
    result = "-1";

    for (int i = 0; i < n; ++i) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int num = Integer.parseInt(st.nextToken());

      ArrayList<Integer> temp = new ArrayList<>();
      for (int j = 0; j < num; ++j) {
        temp.add(Integer.parseInt(st.nextToken()));
      }
      al.add(temp);
    }

    for (int i = 0; i < al.get(0).size(); ++i) {
      visit[0][al.get(0).get(i)] = 1;
      if (dfs(al.get(0).get(i), 1)) {
        chk = 1;
        break;
      }
    }

    if (chk == 1) {
      for (int i = result.length() - 1; i >= 0; --i) {
        bw.write(result.charAt(i) + "\n");
      }
    } else {
      bw.write(result);
    }

    bw.close();
  }

  public static boolean dfs(int prev, int day) throws Exception {
    if (n == day) {
      result = prev + "";
      return true;
    }
    for (int i = 0; i < al.get(day).size(); ++i) {
      if (al.get(day).get(i) == prev || visit[day][al.get(day).get(i)] == 1) {
        continue;
      }
      visit[day][al.get(day).get(i)] = 1;
      if (dfs(al.get(day).get(i), day + 1)) {
        result += prev + "";
        return true;
      }
    }
    return false;
  }
}