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

문제

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

 

 

 

입출력

3
3 1 2 3
2 1 2
2 2 3

 

2
1
3

---

아이디어

 

dfs, 메모이제이션

Map<Key, Value> 

 

 

코드 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static List<Integer>[] riceTypeDay;
	static int[] daySelected;
	static boolean solutionFound = false;
	static Map<String, Boolean> memo = new HashMap<>(); // 메모이제이션을 위한 맵

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		riceTypeDay = new ArrayList[N];

		for (int i = 0; i < N; i++) {
			riceTypeDay[i] = new ArrayList<>();
		}

		// 입력 받기
		StringTokenizer st;
		for (int day = 0; day < N; day++) {
			st = new StringTokenizer(br.readLine());
			int riceTypeCnt = Integer.parseInt(st.nextToken());
			for (int cnt = 0; cnt < riceTypeCnt; cnt++) {
				riceTypeDay[day].add(Integer.parseInt(st.nextToken()));
			}
		}

		daySelected = new int[N]; // 0 ~ N-1 (배열 인덱스 기준)

		// 백트래킹 실행
		if (!backtrack(0, -1)) {
			System.out.println(-1);
		}
	}

	private static boolean backtrack(int day, int prevType) {
		if (solutionFound)
			return true;

		// 모든 날에 대해 선택이 완료된 경우
		if (day == N) {
			solutionFound = true;
			for (int i = 0; i < N; i++) {
				System.out.println(daySelected[i]);
			}
			return true;
		}

		// 메모이제이션 Key 생성
		String key = day + "," + prevType;
		if (memo.containsKey(key))
			return memo.get(key);

		// 오늘 선택 가능한 떡 목록
		List<Integer> riceTypes = riceTypeDay[day];

		// 가능한 떡을 순회하며 선택
		for (int riceType : riceTypes) {
			if (riceType != prevType) { // 연속 선택 방지
				daySelected[day] = riceType;

				if (backtrack(day + 1, riceType)) {// 해당 상태에서 성공적 선택 가능
					memo.put(key, true);
					return true;
				}
			}
		}

		memo.put(key, false); // 해당 상태에서는 유효한 경로가 없음
		return false;
	}
}

메모이제이션 (memo) 적용

• (day, prevType)을 key로 사용하여, 같은 상태에서 중복 연산을 방지.
• 이미 계산된 상태면 즉시 반환하여 불필요한 탐색을 줄임.