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

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static boolean[][] check;
    static int[] result;
    static boolean[] visited;
    static int N, M, cnt;

    public static void main(String[] args) throws IOException {
        init();
        comb(1, 0);
        System.out.println(cnt);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        check = new boolean[N+1][N+1];

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = stoi(st.nextToken());
            int b = stoi(st.nextToken());
            check[a][b] = true;
            check[b][a] = true;
        }

        result = new int[3];
        visited = new boolean[N+1];
    }

    static void comb(int idx, int depth) {
        if(depth == 3)  {
            if(isValid()){
                cnt++;
            }
            return;
        }

        for(int i = idx; i <= N; i++) {
            if(visited[i])continue;
            visited[i] = true;
            result[depth] = i;
            comb(i, depth+1);
            visited[i] = false;
        }
    }
    static boolean isValid() {
        if(!check[result[0]][result[1]] && !check[result[0]][result[2]] && !check[result[1]][result[2]]) {
            return true;
        }
        return false;
    }

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

실버문제 임에도 불구하고 헤매서 다른 분들의 풀이를 보았다..ㅠ 단순한 조합을 사용한 완전탐색 문제였지만 섞이면 안되는 조합 데이터를 저장하는 방법과 탐색이 잘못되어서 계속 메모리초과가 났다.

 

결론적으로는 2차원 배열을 통해서 조합 알고리즘을 통해 만들어진 숫자의 각 자리마다 섞어도 되는 조합인지만 확인하면 되는 문제였다. 계속 풀어보자.