ALGOSPOT - PICINC (java)

https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

오랜만에 풀어서 생각을 제대로 하지 못했습니다. 처음에는 하나의 배열을 만들어 한 줄로 세우고 친구인지 검증하는 방법을 생각하였습니다. 하지만 이 방법은 중복되는 부분이 존재하기 때문에 이를 어떻게 처리해야할 지 고민하다가 책의 풀이를 봤습니다. 

책을 풀이를 보니 배열을 만들 필요가 없었고 제가 생각한 풀이 방법은 중복되는 부분들을 어찌저찌 제거해도 비효율적으로 코드를 작성했을 것이라 생각이 들었습니다. 

책의 풀이는 boolean 배열을 만들어서 사용했는지만 확인하고 순서를 강제하여 중복을 제거하는 것이였습니다.

 

package Algospot;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class Algo_06_PICNIC {
    static int n,m;
    static boolean map[][];
    static boolean visited[];
    static int cal(){
        int first = -1;
        int result = 0;
        for(int i = 0 ; i < n ; i++){
            if(!visited[i]){
                first = i;
                break;
            }
        }
        if(first == -1){
            return 1;
        }
        for(int i = first + 1; i < n ; i++){
            if(!visited[i] && map[first][i]){
                visited[i] = visited[first] = true;
                result += cal();
                visited[i] = visited[first] = false;
            }
        }
        return result;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int test = stoi.apply(st.nextToken());
        for(int t = 0 ; t < test ; t++){
            st = new StringTokenizer(br.readLine()," ");
            n = stoi.apply(st.nextToken());
            m = stoi.apply(st.nextToken());
            map = new boolean[n][n];
            visited = new boolean[n];
            st = new StringTokenizer(br.readLine()," ");
            for(int i = 0 ; i < m ; i++){
                int a = stoi.apply(st.nextToken());
                int b = stoi.apply(st.nextToken());
                map[a][b] = true;
                map[b][a] = true;
            }
            System.out.println(cal());
        }
    }
}