[devmoon]백준 15566 - (Java)개구리1

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

15566번: 개구리 1

1. 유형

구현, 백트래킹

 

2. 시뮬레이션

 

로직

• 각 연꽃마다 앉을 개구리를 매칭 (재귀사용)
• 연결된 연꽃의 개구리 끼리 주제가 맞는지 확인

분류는 백트래킹이지만 단순 구현 비중이 더 큰거 같습니다.

우선 재귀를 사용하여 하나의 연꽃에 하나의 개구리를 매칭시켜야 합니다. 이때 재귀를 사용합니다.

 

모든 개구리가 매칭이 됐으면, 두 연꽃끼리는 하나의 주제가 있습니다.

해당 주제에 대한 개구리들의 관심도가 일치해야 합니다.

 

따라서 2차원 배열을 사용하여 연꽃과 관심도를 저장합니다.

그리고 위의 재귀에서 매칭이 완료된 연꽃,개구리 정보를 사용하여 조건을 해결하는게 가능합니다.

설계

//2차원배열 log[꽃2][꽃2]=주제, frogtype[개구리종류][주제번호]=주제
//꽃[번호]=개구리
//개구리[번호][]=꽃
//주제[개구리][]=레벨

//dfs
//	기저조건
//		주제확인함수
//	for 2:
//		꽃[개구리[dep][i]]=개구리==깊이
//
//주제확인
//	for 꽃N:
//		for 꽃N:
//			통나무연결시: 
//				꽃[번호]=개구리,꽃[번호]=개구리2 
//				타겟관심사확인
//				if 개구리1 관심사!=개구리2관심사:
//					플래그
//					break:
//				else 
//					기록

3. 코드

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

public class Main {
	static int N, M, type[][], frog[][], flower[], log[][];
	static int frogans[];
	static boolean ans;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		type = new int[N][4];
		frog = new int[N][2];
		log = new int[N][N];
		flower = new int[N];
		frogans=new int[N];
		ans=false;
		Arrays.fill(flower, -1);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < 4; j++) {
				type[i][j] = stoi(st.nextToken());
			}
		}
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			frog[i][0] = stoi(st.nextToken()) - 1;
			frog[i][1] = stoi(st.nextToken()) - 1;
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken()) - 1;
			int v = stoi(st.nextToken()) - 1;
			int t = stoi(st.nextToken()) - 1;
			log[u][v] = t;
			log[v][u] = t;
		}
		recursion(0);
		if(ans) {
			System.out.println("YES");
			for(int i=0;i<N;i++)
				System.out.print(frogans[i]+1+" ");
		}
		else
			System.out.println("NO");
	}

	static boolean recursion(int frogindex) {
		if (frogindex == N) {
			if(isValid()) {
				ans=true;
				return true;
			}
			return false;
		}
		for (int i = 0; i < 2; i++) {
			int tempflower = frog[frogindex][i];
			if (flower[tempflower] == -1) {
				flower[tempflower] = frogindex;
				if(recursion(frogindex + 1))
					return true;
				flower[tempflower] = -1;
			}
		}
		return false;
	}

	static boolean isValid() {
		boolean valid = true;
		out: for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i != j && log[i][j] != 0) {
					int f1 = flower[i];
					int f2 = flower[j];
					int target = log[i][j];
					if (type[f1][target] == type[f2][target]) {
						continue;
					} else {
						valid = false;
						break out;
					}
				}
			}
		}
		if(valid)
			frogans=flower.clone();
		return valid;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

4. 느낀점

문제 난이도는 낮지만, 워낙 변수가 많아서 이해하는데 힘들었다.

국어문제