[BOJ] 2644 촌수계산 (Java)

📌 문제

📍 제출 코드

1) BFS - visited boolean형 버전

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_2644_촌수계산_bfs_visited_boolean {

    static int n;
    static int p1, p2;
    static int m;
    static int cnt;
    static int flag;

    static List<Integer>[] graph;
    static boolean[] visited;

    public static int bfs(int x) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, 1));        // 1은 간선의 개수를 구하기위한 인덱스로 사용
        visited[x] = true;
        while(!q.isEmpty()) {
            Point p = q.poll();
            for(int i=0; i<graph[p.x].size(); i++) {
                if(!visited[graph[p.x].get(i)]) {
                    q.add(new Point(graph[p.x].get(i), p.y+1));    // 전 간선의 수 + 1
                    visited[graph[p.x].get(i)] = true;
                    if(graph[p.x].get(i) == p2) {
                        flag = 1;
                        return p.y;
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());    // 사람 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());    // 부모 자식 관계 수

        graph = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        visited = new boolean[n+1];
        int ans = bfs(p1);

        System.out.println(ans);
    }
}

2) BFS - visited int형 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_2644_촌수계산_bfs_visited_int {

    static int n;
    static int p1, p2;
    static int m;

    static List<Integer>[] graph;
    static int[] visited;

    public static int bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visited[x] = 1;        // 방문을 했으면 1을 줌
        while(!q.isEmpty()) {
            int p = q.poll();
            for(int i=0; i<graph[p].size(); i++) {
                int next = graph[p].get(i);        // 다음 노드
                if(visited[next] == 0) {        // 방문을 안했으면
                    q.add(next);
                    visited[next] = visited[p] + 1;    // 간선 수 누적
                    if(next == p2) {
                        return visited[p];
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());    // 사람 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());    // 부모 자식 관계 수

        graph = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        visited = new int[n+1];

        System.out.println(bfs(p1));
    }
}

3) BFS - qSize 버전

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_2644_촌수계산_qSize {

    static int n;
    static int p1, p2;
    static int m;
    static int cnt;
    static int flag;

    static List<Integer>[] graph;
    static boolean[] visited;

    public static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visited[x] = true;
        while(!q.isEmpty()) {
            int qSize = q.size();    // 현재 큐에 들어있는 노드 수만큼 반복
            for(int t=0; t<qSize; t++) {
                int p = q.poll();
                for(int i=0; i<graph[p].size(); i++) {
                    int next = graph[p].get(i);
                    if(!visited[next]) {
                        q.add(next);
                        visited[next] = true;
                        if(next == p2) {
                            flag = 1;    // 연결 체크
                            return;
                        }
                    }
                }
            }
            cnt++;    // 큐사이즈만큼 다 돌고 나서 +1 (즉 한 노드에 연결된 모든 노드를 돌고 +1)
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());    // 사람 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());    // 부모 자식 관계 수

        graph = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        visited = new boolean[n+1];

        bfs(p1);

        if(flag != 1) {
            System.out.println(-1);
        }else {    // 연결된 적이 없으면..
            System.out.println(cnt+1);
        }
    }
}

4) DFS 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_2644_촌수계산_dfs {

    static int n;
    static int p1, p2;
    static int m;
    static int flag = -1;

    static List<Integer>[] graph;
    static boolean[] visited;

    public static void dfs(int x, int cnt) {
        visited[x] = true;
        if (x == p2) {        // 내가 지금 p1이랑 cnt촌이다?!
            flag = cnt;
            return;
        }
        for(int i=0; i<graph[x].size(); i++) {
            int next = graph[x].get(i);
            if(!visited[next]) {
                dfs(next, cnt+1);
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());    // 사람 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());    // 부모 자식 관계 수

        graph = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        visited = new boolean[n+1];

        dfs(p1, 0);

        System.out.println(flag);
    }
}

📝 풀이

• 최단거리 라는 말이 없었기에 bfs, dfs 모두 가능하다. -> 총 4가지 방법으로 풀었다.
• 촌수 계산을 위해서 연결된 두 사람 사이의 간선의 수를 구하면 된다.

💡 Idea

• BFS
  • 전 값까지의 값 + 1 을 해줘 같은 계층에서 간선의 수를 누적해간다.
  • qSize를 이용해 한 노드에 연결된 모든 노드가 큐에서 나갈 때까지, 즉 한 계층을 다 탐색하고나서 +1을 해 간선의 수를 누적해간다.
• DFS
  • 재귀에서 return하면 매개변수에 들어있는 값이 이전 값으로 자동으로 돌아간다는 것을 이용한다.
    매개변수에 cnt를 주고 하나의 노드를 타고 깊이 탐색해가며 +1을 해주고 p2를 발견하면 그때의 cnt값을 출력한다.

💎 새로 알게된 부분

• 2차원 ArrayList[] 배열에 접근할 때 매번 graph[x].get(i) 로 접근하다보니 실수가 잦았다.
•  

int next = graph[x].get(i) 로 선언하고 next 변수로 사용하니 편리했다.

•  
• default값 -1이 있을 때 flag로 처리하지말고 아예 flag에 default값 -1을 준 후 찾는 값이 있을 때 이 flag에 찾은 값을 넣고 main에서는 flag값만 출력하면 간단히 할 수 있다!