백준(BOJ) 9466 : 텀 프로젝트 (JAVA)

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

9466번: 텀 프로젝트

각 노드를 연결했을 때, 순환사이클에 속하지 못하는 노드의 갯수를 구하는 문제이다.

첫번째 풀이를 할 때 고려한 점은 다음과 같다.

1. 누구의 선택도 받지 못한 학생부터 탐색(dfs)을 시작해서 중복 탐색을 제거한다.
2. 순환사이클안에 포함된 노드만 두 번 이상 탐색이 될 것이다.
3. 누구의 선택도 받지 못한 학생에서만 탐색을 시작하기 때문에, 폐쇄된(곁가지가 없는) 순환사이클을 이루는 노드들의 경우(예: 1-> 2-> 3 -> 1) 한 번도 방문되지 않을 것이다.

코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            boolean[] visited = new boolean[n + 1];
            boolean[] revisited = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j]) {
                    boolean[] localVisited = new boolean[n + 1];
                    dfs(selectedIdx, j, localVisited, visited, revisited);
                }
            }
            
            int cnt = 0;
            
            for(int j = 1; j <= n; j++) {
                if(visited[j] && !revisited[j]) {
                    cnt++;
                }
            }
            
            sb.append(cnt + "\n");
        }
        
        System.out.println(sb);
    }
 
    private static void dfs(int[] selectedIdx, int j, boolean[] localVisited, boolean[] visited, boolean[] revisited) {
        if(localVisited[j]) {
            revisited[j] = true;
        } else {
            visited[j] = true;
            localVisited[j] = true;
        }
        
        if(!revisited[selectedIdx[j]]) {
            dfs(selectedIdx, selectedIdx[j], localVisited, visited, revisited);
        }
    }
}

하지만 이 경우, 이미 순환임이 체크된 사이클에 대해 중복된 탐색이 이루어질 수 있는 여지가 있다.

 

필자의 그림 실력을 이해바라며...;; 1번으로 탐색 후에 2번으로 탐색할 경우, 위의 코드로는 또 한번 순환사이클을 체크해야한다.

 

따라서 두 번째로 문제를 풀 때는 다음과 같은 점을 고려했다.

 

1. 순환사이클에 포함되지 않는 노드를 세는 것이 아니라, 순환사이클에 속하는 노드의 갯수를 센 다음 전체에서 빼면 된다.

2. 한번 탐색이 완료된 노드들에 대해서는 표시를 해주고, 중복으로 탐색이 일어나지 않도록 한다.

 

코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            Test test = new Test(selectedIdx, chosen, n);
            
            
            sb.append(test.solve() + "\n");
        }
        
        System.out.println(sb);
    }
    private static class Test {
        private int[] selectedIdx;
        private boolean[] chosen;
        private int n;
        private int teamCnt = 0;
        
        public Test(int[] selectedIdx, boolean[] chosen, int n) {
            this.selectedIdx = selectedIdx;
            this.chosen = chosen;
            this.n = n;
        }
 
        public int solve() {
            boolean[] visited = new boolean[n + 1];
            boolean[] resolved = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j] && !resolved[j]) {
                    dfs(selectedIdx, j, visited, resolved);
                }
            }
                        
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    teamCnt++;
                }
            }
            
            return n - teamCnt;
        }
        
        private void dfs(int[] selectedIdx, int j, boolean[] visited, boolean[] resolved) {
            visited[j] = true;        
            int next = selectedIdx[j];
            
            if(!visited[next]) {
                dfs(selectedIdx, next, visited, resolved);
            } else {
                
                if(!resolved[next]) {
                    
                    for(int i = next; i != j; i = selectedIdx[i]) {
                        teamCnt++;
                    }
                    
                    teamCnt++;
                }            
            }
            
            resolved[j] = true;
        }
    }    
}

필자는 항상 알고리즘 문제를 풀고나면, 내 소스의 걸린 시간 및 메모리를 상위권 사람들과 비교하면서 내가 올바르게 풀었는지의 여부를 판단하는데, 상위권 소스와 같은 로직을 썼음에도 불구하고 시간이 그 사람들처럼 줄어들지 않아서 차이점을 살펴보니, static class를 선언한 후 인스턴스 메서드를 사용하는 것이었다. 구글링을 통해 이유를 검색해보았으나 아직 찾질 못하였으니 혹시 아는 분은 댓글 남겨주시길 간절히 바라옵니다...^^;