백준 9466 번 : 텀 프로젝트 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

텀 프로젝트 골드 3

 

📖 문제

 

그래프 탐색을 하되 Stack + Set 조합으로 풀었다.

 

근데 DFS로 푸는게 정석인가보다.

 

test case

1
4
2 1 2 3

answer : 2
wrong : 무한루프

 

DFS로 다시 풀었을때 시간 초과가 났던 문제의 코드 

    private static void dfs(int current) {
        visited[current] = true;
        int next = students[current];
        if (!visited[next]) {
            dfs(next);

        } else {
            if (finished[next]) return; // 이미 팀 구성을 한 학생이면 더이상 탐색 X

            for (int i = next; i != current; i = students[i]) {
                assignedStudentCnt++;
            }
            assignedStudentCnt++;
        }

        finished[current] = true; // 여기까지 탐색한 모든 학생들은 팀구성 시도를 했다고 표시
    }

 

next 학생이 이미 팀 구성을 했을경우 그냥 return을 해버려 current 학생은 팀 구성 시도를 했음에도 finished[current] = false로 되어버린다. 때문에 

위에서 제시한 테스트 케이스를 보면 무한루프가 될 수 밖에 없다. 

1 - 2 는 팀이 되었지만 

3은 2와 팀이 되고싶고

4는 3과 팀이 되고싶다.

 

3은 탐색때 방문처리되고, finished는 처리되지 않았기에 

학생 4에서 탐색시 next인 3학생은 방문처리되었기에 싸이클이라 판단하고 else 문으로 들억나다.

 

이때 3학생은 finished가 처리되지 않았기에 if문을 지나 for문으로 들어가는데 여기서 시간초과가 발생한다. 

 

i = 4 -> 3 -> 2 -> 1 -> 2 -> 1....           current = 4지만 1과 2가 싸이클이기에 절대 멈추지 않는다. 

 

---

🔅 문제 풀이 [Stack + HashSet]

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine()); // test case

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] students = new int[n + 1];
            boolean[] visited = new boolean[n + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }

            int assignedStudentCnt = 0;

            Stack<Integer> stack = new Stack<>();
            Set<Integer> set = new HashSet<>();

            for (int i = 1; i <= n; i++) {
                if (visited[i]) continue;

                int s = i;
                int wantedStudent = 0;
                while (s != wantedStudent) {
                    if (visited[s]) break; // 팀구성 실패하고 싸이클을 돌 경우 팀구성 취소

                    stack.push(s); // 임시 팀에 합류
                    set.add(s);
                    visited[s] = true; // 방문 처리
                    wantedStudent = students[s]; // s학생이 원하는 학생 대입


                    // 팀구성 조건이 만족하다면 (싸이클)
                    if (!set.contains(wantedStudent)) {
                        // 아직 싸이클 존재 X
                        s = wantedStudent;
                        wantedStudent = 0;
                        continue;
                    }

                    //탐색하면서 현재 학생이 원하는 학생이 임시 팀에 있다면 그 학생까지를 싸이클로 묶어 팀으로 선출
                    while (!stack.isEmpty()) {
                        assignedStudentCnt++; // 팀이 있는 학생 카운트
                        if (stack.pop() == wantedStudent) {
                            break;
                        }
                    }

                    break;
                }

                // 임시 팀 구성 초기화
                stack.clear();
                set.clear();
            }

            bw.write((n - assignedStudentCnt) + "\n");
        }
        bw.flush();
        bw.close();
    }
}

🔅 문제 풀이 [DFS]

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

public class Main {

    static boolean[] visited;
    static boolean[] finished;
    static int[] students;

    static int assignedStudentCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine()); // test case

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            students = new int[n + 1];
            visited = new boolean[n + 1];
            finished = new boolean[n + 1];
            assignedStudentCnt = 0;

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }

            bw.write((n - assignedStudentCnt) + "\n");

        }
        bw.flush();
        bw.close();
    }


    private static void dfs(int current) {
        visited[current] = true;
        int next = students[current];
        
        if (!visited[next]) {
            dfs(next);

			// 싸이클이 발생했을 경우
        } else {
        		// next 즉, 원하는 학생이 팀구성을 안했다면 
            if (!finished[next]) {
                for (int i = next; i != current; i = students[i]) {
                    assignedStudentCnt++;
                }
                assignedStudentCnt++;
            }
        }
		
        // finised[next] = true 일경우에는 현재 학생은 팀을 이룰 수 없지만 팀 구성 시도는 했다고 표시해야 시간초과가 안난다.
        
        finished[current] = true; // 여기까지 탐색한 모든 학생들은 팀구성 시도를 했다고 표시
    }
}

 

 

 

 

❗ 오답노트 / 필요한 지식

1.  방문처리는 정말 중요하다.