백준 2422번

문제

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

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

import java.util.Scanner;

public class Main2422 {
	
	static int N;
	static int M;
	static int[] arr;
	static boolean[] visit;
	static char[] ans;
	static int sum;
	
	public static void compare(int idx, int cnt) {
		
		int count = 0;
		String string1 = "";
		
		if (cnt == 3) {
			string1 = String.valueOf(ans);
			
			System.out.println(string1);
			for (int i=0; i<arr.length-1; i+=2) {
				if (string1.contains(String.valueOf(arr[i])) && string1.contains(String.valueOf(arr[i+1]))) {
					return;
				} 
			}
			
			count++;
			sum += count;

		} else {
			for (int i=idx; i<=N; i++) {
				if (!visit[i]) {
					ans[cnt] = (char)((i)+'0');
					visit[i] = true;
					compare(i+1, cnt+1);
					visit[i] = false;
				}
				
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[M*2];
		visit = new boolean[N+1];
		ans = new char[3];
		
		for (int i=0; i<M*2; i++) {
			arr[i] = sc.nextInt();
		}
		
		sc.close();
		
		compare(1, 0);
		
		System.out.println(sum);
	}

}

import java.util.Scanner;

public class Main2422_1 {
	
	static int N;
	static int M;
	static boolean[][] arr;
	static boolean[] visit;
	static int[] ans;
	static int sum;
	
	public static void compare(int idx, int cnt) {
		
		int count = 0;
		
		if (cnt == 3) {
	
			for (int i=0; i<3; i++) {
				for (int j=i+1; j<3; j++) {
					if (arr[ans[i]][ans[j]]) {
						return;
					}
				}
			}
			
			count++;
			sum += count;

		} else {
			for (int i=idx; i<N; i++) {
				if (!visit[i]) {
					ans[cnt] = i+1;
					visit[i] = true;
					compare(i+1, cnt+1);
					visit[i] = false;
				}
				
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new boolean[N+1][N+1];
		visit = new boolean[N];
		ans = new int[3];
		
		for (int i=0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			arr[a][b] = arr[b][a] = true;
		}
		
		sc.close();
		
		compare(0, 0);
		
		System.out.println(sum);
	}

}

1. 첫번째 코드는 메모리초과로 실패 두번째 코드는 성공

 

2. 메모리 초과는 아마도 M의 범위가 0~10000이기에 arr의 길이가 20000까지 생성되는것이 문제인듯하다.

 

3. 구글링을 통해 여러 글들을 보니 boolean타입의 2차원 배열을 생성하는 것이 핵심이었다.

 

4. 사실 그전에 꽤나 오래 헤맨 부분은 (1,2,3) ,(2,1,3)같은 배열이 중복되기에 이 문제를 해결 하는것이었다. 전에 비슷한 방식으로 풀어본적이 있기에 compare의 매개변수로 idx를 같이 받았다. 하지만 문제는 재귀를 할때 그대로 idx+1을 전했기에 자꾸만 중복된 수가 나온것이었다. 정말 별거 아닌 실수에 시간낭비한 사실이 안타깝다. 항상 급하게 문제를 푸려고 하지말고 천천히 곱씹어 보면서 다가가는 습관을 길들이자.

 

5. 그리고 2차원 배열을 사용해 해결하는 점은 전혀 생각도 못했다. 문제 해결할 때 문자열,배열, 2차원 배열 등 다양한 방법으로 생각하자.