[Baekjoon 3182] 한동이는 공부가 하기 싫어! - JAVA

[Silver III] 한동이는 공부가 하기 싫어! - 3182

문제 링크

성능 요약

메모리: 14348 KB, 시간: 148 ms

분류

브루트포스 알고리즘, 그래프 이론, 그래프 탐색

제출 일자

2023년 11월 19일 12:31:07

문제 설명

H-ALGO 회원인 한동이는 공부하는것을 좋아하지 않는다. 하지만 약삭빠르게도 한동이는 공부도 하지 않으면서 어려운 시험을 통과하고 싶어한다.

그러던 와중 어느 날, 한동이의 동기가 한동이에게 선배들 중 누군가가 시험의 답을 알고있다는 꿀정보를 알려주었다. 하지만 안타깝게도 그 정보는 사실이 아니어서 선배들조차도 정답은 알지 못하고 다른 누군가가 알고 있을거 같다는 정보만 알고 있는 것이었다.

한동이는 택민이에게 시험 정답을 물어보았다. 택민이는 답을 모른다고 했지만 택민이는 상준이가 답을 알고 있을 것 같다고 하였다. 그 후, 한동이는 상준이에게 물어보고 그리고...

어느 순간 한동이는 아무리 이걸 해도 자신에게 도움이 되지 않는것을 깨닫고 굉장히 슬퍼졌다. 하지만 그는 이걸 함으로써 많은 선배들과 인맥을 쌓을 수 있고, 이게 언젠가 큰 도움이 될 것이라는 것을 깨달았다!

당신의 목표는 한동이가 한 사람에게만 시험문제를 물어볼 수 있다고 할 때, 최대한 많은 선배들을 만날 수 있게 하기 위해서 누구에게 시험문제를 물어 볼 것인지를 알려주는 것이다.

입력

입력의 첫 줄에는 정수 N이 주어진다. N은 2이상 1000 이하의 자연수이다. 선배들은 1부터 N까지 번호지어져 있다.

다음 N줄에 하나의 숫자가 주어진다. 첫 번째 줄은 첫 번째 선배의 대답이고 두 번째 줄은 두 번째 선배의 대답이다. 이렇게 N번째 선배의 대답까지 입력이 주어진다.

출력

첫째 줄에 한동이가 물어봐야 할 선배의 번호를 출력한다. 하나 이상의 정답이 있다면 번호가 작은 선배를 출력한다.

문제 풀이

각 선배로부터 출발하여 DFS를 반복하고, 각 선배에 도달할 때마다 연락 수를 증가시키면 된다. 그리고, 그 중 가장 많은 연락 수를 가진 선배를 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] contactGraph;
    static boolean[] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());
        contactGraph = new int[N + 1];
        isVisited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            int contactResponse = Integer.parseInt(reader.readLine());
            contactGraph[i] = contactResponse;
        }

        int maxContacts = 0;
        int personToContact = N + 1;

        for (int i = 1; i <= N; i++) {
            int currentContacts = 0;
            if (contactGraph[i] != 0 && !isVisited[i]) {
                isVisited[i] = true;
                currentContacts = dfs(contactGraph[i], currentContacts);
            }

            if (currentContacts > maxContacts) {
                maxContacts = currentContacts;
                personToContact = i;
            } else if (currentContacts == maxContacts && personToContact > i) {
                personToContact = i;
            }

            initializeVisited();
        }

        System.out.println(personToContact);
    }

    static int dfs(int start, int currentContacts) {
        isVisited[start] = true;
        currentContacts++;

        if (contactGraph[start] != 0 && !isVisited[contactGraph[start]]) {
            currentContacts = dfs(contactGraph[start], currentContacts);
        }

        return currentContacts;
    }

    static void initializeVisited() {
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
    }
}

코드 풀이

int N = Integer.parseInt(reader.readLine());
contactGraph = new int[N + 1];
isVisited = new boolean[N + 1];

for (int i = 1; i <= N; i++) {
    int contactResponse = Integer.parseInt(reader.readLine());
    contactGraph[i] = contactResponse;
}

int maxContacts = 0;
int personToContact = N + 1;

• N: 선배의 수
• contactGraph: 선배 간의 연락을 표현하기 위한 배열
• isVisited: 각 선배의 방문 여부를 확인하기 위한 배열
• contactGraph: 각 선배의 대답을 입력 받을 배열
• maxContacts: 현재까지의 최대 연락 수를 저장하는 변수
• personToContact: 최대 연락 수를 가진 선배의 번호를 저장하는 변수

static int dfs(int start, int currentContacts) {
    isVisited[start] = true;
    currentContacts++;

    if (contactGraph[start] != 0 && !isVisited[contactGraph[start]]) {
        currentContacts = dfs(contactGraph[start], currentContacts);
    }

    return currentContacts;
}

• DFS 함수는 특정 선배로부터 시작하여 연락을 탐색하는 역할을 수행한다.
• start: 현재 선배의 번호를 나타냄
• currentContacts: 현재까지의 연락 수를 저장함
• 방문한 노드는 isVisited 배열을 통해 확인이 가능하다.

static void initializeVisited() {
    for (int i = 0; i < isVisited.length; i++) {
        isVisited[i] = false;
    }
}

• initializeVisited 함수는 isVisited 배열을 초기화하는 역할을 수행한다.
• DFS를 실행한 뒤 방문 여부를 초기화해 다음 선배의 연락을 탐색할 수 있도록 한다.

for (int i = 1; i <= N; i++) {
    int currentContacts = 0;
    if (contactGraph[i] != 0 && !isVisited[i]) {
        isVisited[i] = true;
        currentContacts = dfs(contactGraph[i], currentContacts);
    }

    if (currentContacts > maxContacts) {
        maxContacts = currentContacts;
        personToContact = i;
    } else if (currentContacts == maxContacts && personToContact > i) {
        personToContact = i;
    }

    initializeVisited();
}

System.out.println(personToContact);

• 주어진 선배들을 순회하며 각 선배로부터 DFS를 수행해 연락 수를 계산한다.
• 최대 연락 수를 가진 선배의 번호를 personToContact에 저장하고 출력