[백준_2422번] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

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

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

[문제]

 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

 

[입력 조건]

 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

 

[코드]

import java.util.*;

public class BaekJoon_2422 {
	static boolean[][] graph;
	static int n,m,count=0;
	static boolean[] visited;
	static int[] icecream=new int[3];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		visited=new boolean[n+1];
		graph=new boolean[n+1][n+1];
		
		// 섞으면 안 되는 조합의 배열 값을 true로 변경한다.  
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			graph[a][b]=graph[b][a]=true;
		}
		
		dfs(0,1);
		System.out.println(count);
	}
	
	public static void dfs(int depth,int start) {
		/*
		 * 3개의 아이스크림을 골랐다면 3개의 맛 중 2개씩 선택하여
		 * 섞으면 안되는 조합에 해당하는지 체크한다.
		 */
		if(depth==3) {
			for(int i=0;i<3;i++) {
				for(int j=i+1;j<3;j++) {
					// graph 값이 true라면 섞으면 안되는 조합
					if(graph[icecream[i]][icecream[j]])
						return;
				}
			}
			// 섞으면 안되는 조합에 해당하지 않는다면 해당 경우의수 count
			count++;
			return;
		}
		
		/*
		 * n개의 아이스크림 중 3개를 중복 없이 골라야 하기 때문에 
		 * i의 시작점을 늘려가며 백트래킹을 해야한다.  
		 * i를 다시 1부터 시작하게 되면 (1,2,3)과 같은 경우의 수인 (2,3,1), (3,2,1)등이 고려되기 떄문이다.
		 */
		for(int i=start;i<=n;i++) {
			if(visited[i]==false) {
				visited[i]=true;
				icecream[depth]=i;
				dfs(depth+1,i+1);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 백준 2530번 숫자야구와 같은 유형의 문제였다. 고를 수 있는 아이스크림의 경우의 수를 모두 탐색해보는 방법으로 해결할 수 있는 완전탐색 문제로 이때 주의해야할 점은 (1, 2, 3) 아이스크림을 고르는 경우와 (2, 1, 3) 아이스크림을 고르는 경우는 같은 상황이라는 것이다. 따라서 중복 없이 선택하기 위해 dfs 함수에 start 매개변수를 하나 더 추가하여 재귀함수에서는 start 이후의 배열 값을 선택하도록 해야한다. 

 또한 선택하면 안 되는 조합의 아이스크림의 번호를 처음에는 클래스로 선언하여 연결리스트에 담고, 3개의 아이스크림을 골랐을때 연결리스트에 저장된 모든 조합을 검사하는 방식으로 해결했었는데 시간초과를 받았다. 그래서 연결리스를 모두 탐색하는 방식이 아닌 주어지는 조합을 그래프로 생각했다. 주어진 두 가지의 아이스크림의 배열 값을 true로 바꿔놓고 선택한 3가지의 아이스크림 중 2개씩 선택하여 배열 값이 true인지 검사하는 방법으로 코드를 짰더니 시간초과 없이 정답처리를 받을 수 있었다.