πŸ”₯[99클럽 μ½”ν…Œ μŠ€ν„°λ””] 17일차 TIL - μ΄Œμˆ˜κ³„μ‚°

HOONSSACΒ·2024λ…„ 8μ›” 7일
1

99Club Coding Test Study

λͺ©λ‘ 보기
17/41
post-thumbnail

⏳문제

우리 λ‚˜λΌλŠ” κ°€μ‘± ν˜Ήμ€ μΉœμ²™λ“€ μ‚¬μ΄μ˜ 관계λ₯Ό μ΄Œμˆ˜λΌλŠ” λ‹¨μœ„λ‘œ ν‘œν˜„ν•˜λŠ” λ…νŠΉν•œ λ¬Έν™”λ₯Ό 가지고 μžˆλ‹€. μ΄λŸ¬ν•œ μ΄Œμˆ˜λŠ” λ‹€μŒκ³Ό 같은 λ°©μ‹μœΌλ‘œ κ³„μ‚°λœλ‹€. 기본적으둜 λΆ€λͺ¨μ™€ μžμ‹ 사이λ₯Ό 1촌으둜 μ •μ˜ν•˜κ³  μ΄λ‘œλΆ€ν„° μ‚¬λžŒλ“€ κ°„μ˜ 촌수λ₯Ό κ³„μ‚°ν•œλ‹€. 예λ₯Ό λ“€λ©΄ λ‚˜μ™€ 아버지, 아버지와 ν• μ•„λ²„μ§€λŠ” 각각 1촌으둜 λ‚˜μ™€ ν• μ•„λ²„μ§€λŠ” 2촌이 되고, 아버지 ν˜•μ œλ“€κ³Ό ν• μ•„λ²„μ§€λŠ” 1촌, λ‚˜μ™€ 아버지 ν˜•μ œλ“€κ³ΌλŠ” 3촌이 λœλ‹€.

μ—¬λŸ¬ μ‚¬λžŒλ“€μ— λŒ€ν•œ λΆ€λͺ¨ μžμ‹λ“€ κ°„μ˜ 관계가 μ£Όμ–΄μ‘Œμ„ λ•Œ, 주어진 두 μ‚¬λžŒμ˜ 촌수λ₯Ό κ³„μ‚°ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

μ‚¬λžŒλ“€μ€ 1, 2, 3, …, n (1 ≀ n ≀ 100)의 μ—°μ†λœ 번호둜 각각 ν‘œμ‹œλœλ‹€. μž…λ ₯ 파일의 첫째 μ€„μ—λŠ” 전체 μ‚¬λžŒμ˜ 수 n이 주어지고, λ‘˜μ§Έ μ€„μ—λŠ” 촌수λ₯Ό 계산해야 ν•˜λŠ” μ„œλ‘œ λ‹€λ₯Έ 두 μ‚¬λžŒμ˜ λ²ˆν˜Έκ°€ 주어진닀. 그리고 μ…‹μ§Έ μ€„μ—λŠ” λΆ€λͺ¨ μžμ‹λ“€ κ°„μ˜ κ΄€κ³„μ˜ 개수 m이 주어진닀. λ„·μ§Έ μ€„λΆ€ν„°λŠ” λΆ€λͺ¨ μžμ‹κ°„μ˜ 관계λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 두 번호 x,yκ°€ 각 쀄에 λ‚˜μ˜¨λ‹€. μ΄λ•Œ μ•žμ— λ‚˜μ˜€λŠ” 번호 xλŠ” 뒀에 λ‚˜μ˜€λŠ” μ •μˆ˜ y의 λΆ€λͺ¨ 번호λ₯Ό λ‚˜νƒ€λ‚Έλ‹€.

각 μ‚¬λžŒμ˜ λΆ€λͺ¨λŠ” μ΅œλŒ€ ν•œ λͺ…λ§Œ 주어진닀.

좜λ ₯

μž…λ ₯μ—μ„œ μš”κ΅¬ν•œ 두 μ‚¬λžŒμ˜ 촌수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜λ₯Ό 좜λ ₯ν•œλ‹€. μ–΄λ–€ κ²½μš°μ—λŠ” 두 μ‚¬λžŒμ˜ μΉœμ²™ 관계가 μ „ν˜€ μ—†μ–΄ 촌수λ₯Ό 계산할 수 없을 λ•Œκ°€ μžˆλ‹€. μ΄λ•Œμ—λŠ” -1을 좜λ ₯ν•΄μ•Ό ν•œλ‹€.

μž…μΆœλ ₯ 예

예제 μž…λ ₯ 1

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 좜λ ₯ 1

3

예제 μž…λ ₯ 2

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 좜λ ₯ 2

-1

βœοΈν’€μ΄

일단, 주어진 예제 μž…λ ₯ 1을 κ·Έλž˜ν”„λ‘œ ν‘œν˜„ν•΄ λ³΄μ•˜μ„ λ•Œ, 두 개의 κ·Έλž˜ν”„ ν˜•νƒœλ‘œ λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€.
그런데 μ—¬κΈ°μ„œ 문제 쑰건 쀑 촌수λ₯Ό 계산해야 ν•˜λŠ” μ„œλ‘œ λ‹€λ₯Έ 두 μ‚¬λžŒμ˜ λ²ˆν˜Έκ°€ 각각 λ‹€λ₯Έ κ·Έλž˜ν”„μ— μ†ν•œλ‹€λ©΄, μ΄Œμˆ˜κ°€ μ ˆλŒ€ μ΄μ–΄μ§ˆ 수 μ—†λŠ” κ΅¬μ‘°μ΄λ―€λ‘œ 이 κ²½μš°μ—λŠ” μ΅œμ’…μ μœΌλ‘œ -1을 λ°˜ν™˜ν•΄μ•Ό ν•œλ‹€.

이 λ¬Έμ œλŠ” DFS와 BFS둜 λ‘˜ λ‹€ ν’€ 수 μžˆμ§€λ§Œ, λ‚˜λŠ” DFS 방식을 택해 ν’€μ–΄λ³΄κΈ°λ‘œ ν–ˆλ‹€.

예제 μž…λ ₯ 1을 계속 μ˜ˆμ‹œλ‘œ λ“€μ–΄λ³΄μ•˜μ„ λ•Œ, DFS의 좜발 지점은 7번 λ…Έλ“œκ°€ λœλ‹€.
이제 3번 λ…Έλ“œλ₯Ό μ°Ύμ•„κ°€λŠ” 길이 μ–΄λ–»κ²Œ λ˜λŠ” 지 ν•œ 번 μ•Œμ•„λ΄μ•Όκ² λ‹€.

λ¨Όμ €, 7번 λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” κ²½μš°λŠ” 2번 λ…Έλ“œλ°–μ— μ—†λ‹€.

λ‹€μŒμœΌλ‘œ, 2번 λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” κ²½μš°λŠ”
1번 λ…Έλ“œλ„ 있고, 8번 λ…Έλ“œλ„ 있고, 9번 λ…Έλ“œλ„ μžˆλ‹€.
근데 DFSλ₯Ό μ½”λ“œλ‘œ κ΅¬ν˜„ν•  λ•ŒλŠ” 보톡 μΈλ±μŠ€κ°€ μž‘μ€ μˆœμ„œλŒ€λ‘œ λ¨Όμ € λ°©λ¬Έν•˜λ„λ‘ λ˜μ–΄μžˆκΈ° λ•Œλ¬Έμ—, 1번 λ…Έλ“œλ₯Ό λ°©λ¬Έν•œλ‹€κ³  κ°€μ •ν•˜μž.

κ·Έλ ‡λ‹€λ©΄, 이제 1번 λ…Έλ“œμ—μ„œ 3번 λ…Έλ“œλ‘œ 갈 수 μžˆλŠ” 길이 μ‘΄μž¬ν•œλ‹€.
λ”°λΌμ„œ, 7번 λ…Έλ“œμ—μ„œ 2번 λ…Έλ“œλ‘œ, 2번 λ…Έλ“œμ—μ„œ 1번 λ…Έλ“œλ‘œ, 1번 λ…Έλ“œμ—μ„œ 3번 λ…Έλ“œλ‘œ,
총 3번 λ…Έλ“œλ₯Ό 거쳐가기 λ•Œλ¬Έμ— μ΅œμ’…μ μœΌλ‘œ 3이 λ°˜ν™˜λ˜κ³ , μ΄λŠ” 3μ΄Œμ΄λΌλŠ” λœ»μ΄μ–΄μ•Ό ν•œλ‹€.

그런데 DFSλŠ” 아직 λλ‚˜μ§€ μ•Šμ•˜κΈ° λ•Œλ¬Έμ—, 2번 λ…Έλ“œμ—μ„œ 8번 λ…Έλ“œλ₯Ό νƒμƒ‰ν•˜λŠ” 과정을 κ±°μΉ  것이닀. 이 λ•Œ, 8번 λ…Έλ“œμ—μ„œλŠ” 더 이상 μžμ‹ λ…Έλ“œκ°€ μ—†κΈ° λ•Œλ¬Έμ— -1을 λ°˜ν™˜ν•  것이고, 9번 λ…Έλ“œλ„ λ§ˆμ°¬κ°€μ§€μΌ 것이닀.

πŸ–₯οΈμ΅œμ’… μ½”λ“œ

import java.io.IOException;
import java.util.Scanner;

public class Main {
    int[][] graph; // 관계도
    boolean[] visited; // λ…Έλ“œ λ°©λ¬Έ μ—¬λΆ€ μ €μž₯
    int N; // 전체 인원

    public void solve() throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 전체 인원 μž…λ ₯
        sc.nextLine(); // 버퍼 λΉ„μš°κΈ°

        // 촌수λ₯Ό 확인할 μ„œλ‘œ λ‹€λ₯Έ 두 μ‚¬λžŒ μž…λ ₯
        String[] Search = sc.nextLine().split(" ");
        int p1 = Integer.parseInt(Search[0]);
        int p2 = Integer.parseInt(Search[1]);

        int M = sc.nextInt(); // 관계 개수 μž…λ ₯
        sc.nextLine(); // 버퍼 λΉ„μš°κΈ°

        // graph, visitied μΈμŠ€ν„΄μŠ€ 생성
        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        // 관계 μž…λ ₯
        for (int i = 0; i < M; i++) {
            String[] input = sc.nextLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);

            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        // p1μ—μ„œλΆ€ν„° dfs μ‹œμž‘
        System.out.print(dfs(p1, p2, 0));
        sc.close();
    }

    public int dfs(int now, int dest, int chon) {
        if (now == dest) {
            return chon; // 찾을 두 μ‚¬λžŒμ΄ κ°™λ‹€λ©΄ chon λ°˜ν™˜
        }

        visited[now] = true; // ν˜„μž¬ λ…Έλ“œ λ°©λ¬Έ ν‘œκΈ°

        int r = -1; // μ΄ˆκΈ°κ°’ : -1

        for (int i = 1; i <= N; i++) {
            if (graph[now][i] == 1 && visited[i] == false) {
                int subR = dfs(i, dest, chon + 1); // λ‹€μŒ λ…Έλ“œ λ°©λ¬Έ
                if (subR != -1 && subR >= r) { // 찾은 λͺ©μ μ§€κΉŒμ§€μ˜ 촌수 μ—…λ°μ΄νŠΈ
                    r = subR;
                }
            }
        }

        return r;
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solve();
    }
}


πŸ”—λ¬Έμ œ 링크
πŸ’»Repository

profile
ν›ˆμ‹Ήμ˜ κ°œλ°œμ—¬ν–‰

1개의 λŒ“κΈ€

comment-user-thumbnail
2024λ…„ 8μ›” 8일

으렀브으렀브πŸ€ͺ

λ‹΅κΈ€ 달기