[백준]16234 떡장수와 호랑이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B16432 {
	static int N, K;
	static boolean flag;
	static int arr[][], dp[];
	static boolean[][] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		arr = new int[N][10];
		visit = new boolean[N+1][10];
		dp = new int[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			K = Integer.parseInt(st.nextToken());
			for (int j = 0; j < K; j++) {
				arr[i][Integer.parseInt(st.nextToken())] = 1;
			}
		}
		
		get(0,0);
		
		if(flag) {
			for(int i=0;i<N;i++) {
				sb.append(dp[i]).append("\n");
			}
		}else sb.append(-1);
		
		System.out.println(sb);
	}
	
	private static void get(int num, int next) {
		if(next==N) {
			flag = true;
			return;
		}
		
		for (int i = 1; i < 10; i++) {
			/// 이전 값과 비교하고 다음 값 있는지 확인
			if(num==i) continue;
			if(arr[next][i]==1 && !visit[next+1][i]) {
				// 재방문해도 아래쪽 결과는 같으므로 다시 방문하지 않아도 됨
				visit[next+1][i] = true;
				dp[next]=i;
				get(i,next+1);
				if(flag) return;
				
			}
		}
	}
}