[백준] 15566. 개구리1 (자바 JAVA)

[ 문제 ]  [백준] 15566. 개구리1 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/15566

15566번: 개구리 1

---

# 접근 방법 및 풀이 

 

• 완탐 + 백트래킹으로 풀었다.
• 개구리는 최대 N개고 각 개구리마다 선호하는 연꽃번호는 1~2개씩 있다.
• 각 개구리마다 선호하는 연꽃으로 선택해서 연꽃마다 개구리 배치를 다 해준다. 이때 개구리를 연꽃에 배치하는 모든 경우의 수는 개구리마다 선택지가 각 최대 2개씩이므로 2^N이다.  
• N이 최대 15이고, 2^15면 완탐으로 다 뽑아도 시간초과 범위 안이다.
• 개구리를 연꽃에 다 배치해준 다음에, 통나무 정보대로 각 연꽃에 위치해있는 개구리들의 주제의 흥미도가 같은지 검사해준다.
• 흥미도 검사까지 다 해서 그배치가 가능하다면 YES를 입력하고 배치한 개구리 번호를 출력하고 종료시켜주었다.
• M은 최대 100이고, "개구리를 연꽃에 배치해보는 모든 경우의수 x M번의 통나무 정보 탐색"을 하면,
• 시간복잡도는 최대 2^15 X 100이다.
• 자세한건 코드참조

 

 

# 주의할 점 

 

•  어떤 개구리가 선호하는 연꽃이 하나라면 A = B이다. 처리해주기. 난 같은 번호면 -1이라고 값을 넣어주고 이부분은 continue했다.
• 개구리 배치할 때 idx때문에 헷갈리는데, 개구리가 가고자하는 자리인 num에 해당 개구리를 위치시켜주기.

 

JAVA 코드

package Silver;

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

public class bj15566_개구리1 {
	static int N, M, frog[][], like[][], tree[][];
	static int sel[];
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		frog = new int[N][4];
		like = new int[N][2];
		tree = new int[M][3];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < 4; j++) {
				frog[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			like[i][0] = Integer.parseInt(st.nextToken()) - 1;
			like[i][1] = Integer.parseInt(st.nextToken()) - 1;
			if (like[i][0] == like[i][1])
				like[i][1] = -1;
		}
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < 3; j++) {
				tree[i][j] = Integer.parseInt(st.nextToken())-1;
			}
		}
		String ans = "NO";
		sel = new int[N];
		visit = new boolean[N];
		dfs(0);
		System.out.println(ans);
	}


	private static void dfs(int idx) {
		if (idx == N) {
			if (check()) {
				System.out.println("YES");
				for (int i = 0; i < N; i++)
					System.out.print((sel[i]+1) + " ");
				System.exit(0);
			}
			return;
		}

		for (int j = 0; j < 2; j++) {
			if (like[idx][j] == -1)
				continue;
			int num = like[idx][j];
			if (!visit[num]) {
				visit[num] = true;
				sel[num] = idx;
				dfs(idx + 1);
				visit[num] = false;
			}
		}

	}

	private static boolean check() {
		for (int i = 0; i < tree.length; i++) {
			int a = tree[i][0];
			int b = tree[i][1];
			int like = tree[i][2];
			int frog1 = sel[a];
			int frog2 = sel[b];
			if(frog[frog1][like] != frog[frog2][like])
				return false;
		}
		return true;
	}
}

 

 

 

REVIEW

설연휴라고 알고리즘 일주일 쉬었더니 감 잃은게 느껴진다..미쳤다

백준 선생님께서 브루트포스 풀어야할 문제집 집어주셔서 하나씩 풀어보려고했더니.. 정답률 낮아서 겁먹었음

정신 차려라.