[백준]16432: 떡장수와 호랑이 - JAVA

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

www.acmicpc.net/problem/16432

16432번: 떡장수와 호랑이

풀이

전형적인 DFS 탐색 문제로 문제의 조건에 따라 이전에 뽑은 숫자와 다른 숫자를 N만큼 뽑을 수 있다면 뽑은 수를 출력하고, 뽑을 수 없다면 -1을 출력하면 된다.

 

간단하게 DFS를 사용하여 구현하였다. 그리고 N개를 뽑을 수 있는 방법이 여러개라면 한 개만 출력하면 되므로 N개를 뽑고 출력한 다음 프로그램을 종료시켰다.

 

만약 DFS를 돌면서 N개를 뽑지 못하고 DFS함수가 종료되었다면 -1을 출력해 주도록 하였다.

 

현재 날짜와 이전의 뽑은 수를 기억하기 위해 boolean배열을 2차원으로 선언해 주었다. 각각의 인덱스는 [n번째 날][떡의 종류]를 의미한다.

 

DFS함수에서는 1 ~ 10번 까지 수를 뽑고, 그 중에 이전에 뽑은 수가 아니고(i != prev) 방문한 적이 없으며(visited[idx + 1][i] == false) 해당 수가 해당 날짜에 뽑을 수 있는 수라면(list[idx].contains(Integer(i))) 해당 방향으로 DFS탐색을 진행한다.

 

코드

import java.util.*;
 
public class Main {    
 
    static ArrayList<Integer>[] list;
    static boolean[][] visited;
    static int[] result;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<>();
            int m = scan.nextInt();
            for(int j = 0; j < m; j++) {
                list[i].add(scan.nextInt());
            }
        }
        
        result = new int[n + 1];
        visited = new boolean[n + 2][10]; //[n번째 날][떡의 종류]
        dfs(1, 0, n);
        System.out.println("-1");
        
    }    
    
    public static void dfs(int idx, int prev, int n) {
        if(idx == n + 1) {
            for(int i = 1; i < n + 1; i++) {
                System.out.println(result[i]);
            }
            System.exit(0);
        }
    
        for(int i = 1; i < 10; i++) {
            if(i != prev && visited[idx + 1][i] == false && list[idx].contains((Integer)i)) {
                visited[idx + 1][i] = true;
                result[idx] = i;
                dfs(idx + 1, i, n);
            }
        }
    }
}