[JAVA 알고리즘]BAEKJOON 16432번 떡장수와 호랑이

생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 16432번 떡장수와 호랑이

생각중임 2024. 1. 3. 23:18

DFS를 이용해서 문제를 해결하는 문제

떡장수와 호랑이

문제 설명

떡장수 동희는 매일 새벽에 갓 만든 떡을 들고 산을 넘어 장터로 가서 떡을 팝니다. 동희가 만드는 떡의 종류는 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' 하나만 출력하고 더 이상 아무것도 출력하지 않아야 합니다.

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

입출력 예

input	return
3 3 1 2 3 2 1 2 2 2 3	2 1 3
3 3 7 8 9 1 1 1 1	-1

나의 문제풀이

import java.io.*;
import java.util.*;
 
public class Main {    
 
    static List<Integer>[] riceCake;
    static int[] eat;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(bufferedReader.readLine());
        // 입력값 넣을 리스트 배열
        riceCake = new List[N];
        // 출력값 저장할 배열
        eat = new int[N];
        // 일자 별로 떡 종류 확인할 배열
        visited = new boolean[N][10];
        // 입력값을 반복해 리스트 배열에 넣는다.
        for (int i = 0; i < N; i++) {
            riceCake[i] = new ArrayList<>();
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int index = Integer.parseInt(stringTokenizer.nextToken());
            for (int j = 0; j < index; j++) {
                riceCake[i].add(Integer.parseInt(stringTokenizer.nextToken()));
            }
        }

        dfs(N-1, 0);
        
        // 첫날에 떡을 주지 못 했으면 떡을 줄 방법이 없기때문에 -1
        if (eat[0] == 0) {
            System.out.println("-1");
        } else { // 첫날에 떡을 줬다면 호랑이가 먹은 떡을 출력
            for (int i : eat) {
                System.out.println(i);
            }
        }
    }

    public static void dfs(int day, int before) {
        // 첫날이 지나면 종료
        if (day < 0) return;

        for (int cake : riceCake[day]) {
            // 전날 준 떡이 아니고 해당 날에 준 떡이 아닌지 확인
            if (!visited[day][cake] && cake != before) {
                visited[day][cake] = true;

                dfs(day - 1, cake);

                eat[day] = cake;
            }
            // 첫날에 떡을 준 적이 있으면 종료
            if (eat[0] != 0) break;
        }
    }
}

입력값이 일별로 떡의 종류를 넣기 위해 리스트를 배열에 넣어준다.
출력값을 저장할 배열을 선언한다.
일자 별로 떡의 종류를 확인할 배열을 선언한다.
마지막 날부터 첫 날까지 반복한다.
- 해당 날의 떡을 반복하면서 이전에 준 떡이 아니고 해당 날에 준 적 있는 떡의 종류가 아니면 사용으로 확인하고 전날로 반복한다.
- 준 떡을 eat배열에 넣어준다.
- 첫날이 지나면 재귀를 종료시켜 준다.
- 첫날에 떡을 준 적이 있으면 반복을 종료시킨다.
eat배열에 첫날의 값이 들어가 있으면 eat배열을 출력하고 아니면 -1을 출력한다.

입력값이 날짜와 떡의 종류로 2가지 있는 걸 확인을 하고 이차배열을 사용하는 것과 DFS를 구현하는 것이 포인트인 문제인 것 같다.
해당 문제를 풀 때는 마지막부터 첫날로 반복을 하도록 했는데, 첫날 부터 마지막날로 반복을 해도 상관은 없다. 단순 일자 부분과 종료 부분만 바꾸면 다른 부분은 동일하게 사용해도 된다.
마지막 부터 첫날로 풀게 된 건 처음에 문제를 잘 못 보고 입력 값 자체를 두 번째 줄부터 떡의 개수와 떡의 종류를 입력해 주는데 전부다 떡의 종류인지 알고 떡의 숫자를 모르니 리스트를 이용해서 입력을 하도록 하고 반복을 시켜 잘 못된 값으로 반복을 시켜 정답이 제대로 나오지 않았다.
문제를 좀 더 재대로 읽고 들어가야 시간을 이상한데 많이 소비하지 않을 것 같다. 조심하자.