[BOJ] 16432. 떡장수와 호랑이

DFS를 이용하는 문제였다.

맨처음 문제를 접했을때 아무생각없이 바로 DFS를 적용해봤는데, 역시나 최악의 경우 8^1000(전날의 떡을제외한 경우^날짜수)이 나오기때문에 시간초과를 면할 수 없었다. 그래서 바로 방문체크로 가지치는 방법을 택해주었다. visit[i번째날][떡]을 하나 만들어서 만일 이전날의 떡과 다르면서 visit[오늘][떡]이 방문 가능하다면 방문을 하고 방문체크를 해주는 방식으로 구현해보았다. 이렇게 된다면 어떠한 방식으로든 오늘에서 가질수 있는 떡을 중복으로 방문하는 것을 막을 수 있게 된다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_16432_떡장수와호랑이 {
    static int N;
    static boolean[][] graph;
    static int[] result;
    static boolean find;
    static boolean[][] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        graph = new boolean[N][10];
        result = new int[N];
        visit = new boolean[N][10];        //N번째 날에 i번의 떡을 가지는 경우를 체크
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            for (int n = 0; n < num; n++) {
                graph[i][Integer.parseInt(st.nextToken())] = true;
            }
        }
 
        find = false;
        dfs(0, -1);
 
        StringBuilder sb = new StringBuilder();
        if (find) {
            for (int i = 0; i < N; i++) {
                sb.append(result[i] + " ");
            }
            System.out.println(sb.toString());
        } else {
            System.out.println(-1);
        }
    }
 
    static void dfs(int depth, int previousNum) {
        if (find == true) {
            return;
        }
 
        if (depth == N) {
            find = true;
            return;
        }
 
        for (int i = 1; i <= 9; i++) {
            if (graph[depth][i] == true && i != previousNum && visit[depth][i] == false && find == false) {
                result[depth] = i;
                visit[depth][i] = true;
                dfs(depth + 1, i);
            }
        }
 
    }
}