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

hyunnzl·2025년 7월 1일

백준

목록 보기

87/116

https://www.acmicpc.net/problem/16432

난이도

골드 4

문제

떡장수 동희는 매일 새벽에 갓 만든 떡을 들고 산을 넘어 장터로 가서 떡을 팝니다. 동희가 만드는 떡의 종류는 1번부터 9번까지 있습니다.

산에는 동희가 나타나기를 기다렸다가 동희를 협박하여 떡을 하나 가져가는 호랑이가 살고 있습니다. 이 호랑이는 입맛이 까다로워 전날에 먹었던 떡과 같은 종류의 떡이면 먹지 않습니다. 만약 줄 수 있는 떡이 없다면 동희는 호랑이에게 잡아먹히고 맙니다.

동희는 N일 동안 떡을 팔러 매일 장터에 나가야 합니다. 동희가 만드는 떡들의 종류는 재료 공급 사정에 따라 종류가 매일 달라집니다.

동희가 N일 동안 호랑이에게 잡아먹히지 않도록 호랑이에게 줄 떡들을 골라주세요.

입력

첫 번째 줄에 동희가 떡을 팔아야 할 날의 수 N이 (1 ≤ N ≤ 1,000) 이 주어집니다.

i+1 (1 ≤ i ≤ N) 번째 줄에는 mi, ai,1, ai,2, ..., ai,mi (1 ≤ mi ≤ 9, 1 ≤ ai,1 < ai,2 < ... < ai,mi ≤ 9) 가 주어지는데 mi는 동희가 i번째 날 들고 가는 떡들의 개수이고 ai,j는 동희가 가져가는 떡의 종류입니다.

출력

동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다.

만약 동희가 떡을 줄 방법이 없다면 첫 번째 줄에 '-1' 하나만 출력하고 더 이상 아무것도 출력하지 않아야 합니다.

방법이 여러 가지인 경우 그 중 하나만 출력합니다.

내 코드

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

class Main {

    static int day;
    static ArrayList<Integer>[] food;
    static int[] answer;
    static boolean[][] visited;
    static boolean found = false;
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        day = Integer.parseInt(br.readLine());

        food = new ArrayList[day];
        for(int i = 0; i < day; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            
            food[i] = new ArrayList<>();
            for(int j = 0; j < N; j++){
                food[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        answer = new int[day];
        visited = new boolean[day][11];
        
        dfs(0, 0);

        if(!found){
            System.out.println(-1);
        }
    }

    public static void dfs(int now, int prev){
        if(found){
            return;
        }

        if(now == day){
            for(int i = 0; i < day; i++){
                System.out.println(answer[i]);
            }
            found = true;
            return;
        }

        if(visited[now][prev]) return;
        visited[now][prev] = true;

        for(int n : food[now]){
            if(n == prev) continue;

            answer[now] = n;
            dfs(now + 1, n);
        }
    }
}