[Java] 백준 - 2644번: 촌수계산

11월 17일(금) - 그래프와 순회 (2644번)

2644번: 촌수계산

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(dfs 풀이출처 -> https://eijun.tistory.com/273 )

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

import java.util.*;

public class Main {

    static int N,from,to,result = -1;
    static boolean[][] map;
    static boolean[] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        from = Integer.parseInt(st.nextToken());
        to = Integer.parseInt(st.nextToken());

        map = new boolean[N+1][N+1];
        int M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++)
        {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            map[v1][v2] = map[v2][v1] = true;
        }

        visited = new boolean[N+1];

        dfs(from, 0);
        System.out.println(result);
    }

    private static void dfs(int p, int d){
        visited[p] = true;

        if(p == to)
        {
            result = d;
            return;
        }

        for(int i=1; i<=N; i++)
        {
            if(map[p][i] && !visited[i])
            {
                dfs(i, d+1);
            }
        }
    }

}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(bfs 풀이출처 -> https://velog.io/@topqr123q/백준-2644번-자바 )

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

import java.util.*;

public class Main {

    static int N,from,to,result = -1;
    static int[][] map;
    static boolean[] visited;

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

        N = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        visited = new boolean[N+1];

        st = new StringTokenizer(br.readLine());
        from = Integer.parseInt(st.nextToken());
        to = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        for(int i=0; i<M; i++)
        {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            map[v1][v2] = map[v2][v1] = 1;
        }

        System.out.println(bfs(from,to));
    }

    static int bfs(int p1, int p2){
        int result = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(p1);

        while (!q.isEmpty())
        {
            int size = q.size();
            for(int i=0; i<size; i++)
            {
                int cur = q.poll();
                visited[cur] = true;
                if(cur == p2)
                {
                    return result;
                }
                for(int child=1; child<=N; child++)
                {
                    if(map[cur][child] == 1)
                    {
                        if(!visited[child])
                        {
                            q.add(child);
                        }
                    }
                }
            }

            result++;
        }
        return -1;
    }

}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ