BOJ_2644 : 촌수계산

👉 문제링크

2644번: 촌수계산

---

---

🔸 문제 분석 🔸

• 노드 수 n, 시작 노드, 끝 노드, 간선의 수 m과 m개의 간선 정보가 입력된다.
• 시작 노드부터 끝 노드 까지 몇 개의 간선으로 갈 수 있는지 출력한다.
  • 연결되어있지 않으면 -1을 출력한다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> arr[] = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }

        int h1 = sc.nextInt();
        int h2 = sc.nextInt();
        int m = sc.nextInt();

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (!arr[x].contains(y)) {
                arr[x].add(y);
                arr[y].add(x);
            }
        }
        System.out.println(bfs(arr, h1, h2));
    }

    private static int bfs(ArrayList<Integer>[] arr, int h1, int h2) {
        boolean[] visit = new boolean[arr.length + 1];
        Stack<Person> stack = new Stack<>();
        stack.push(new Person(h1, 0));

        while (!stack.isEmpty()) {
            Person p = stack.pop();
            if (!visit[p.idx]) {
                if (p.idx == h2) {
                    return p.count;
                }

                visit[p.idx] = true;
                for (int i = 0; i < arr[p.idx].size(); i++) {
                    stack.push(new Person(arr[p.idx].get(i), p.count + 1));
                }
            }
        }
        return -1;
    }

    private static class Person {
        int idx;
        int count;

        Person(int idx, int count) {
            this.idx = idx;
            this.count = count;
        }
    }
}

🔸 코드 해석 🔸

• 노드 정보와 간선 정보를 입력 받고 BFS로 탐색한다.
• Person 클래스를 만들어 인덱스와 현재까지의 간선 수를 저장한다.
• bfs메서드에서 탐색을 수행하고 인덱스를 반환한다.
  • 노드 방문을 확인할 boolean 배열 visit과 bfs를 위한 Person 스택 stack을 선언한다.
  • 시작 노드의 인덱스 h1을 스택의 초기값으로 넣는다.
  • 스택이 빌 때까지 계산을 반복한다.
    • 스택에서 값을 pop
    • 방문한적이 없는 노드면, 끝 노드인지 확인
    • 끝노드가 아니면 visit을 true로 바꾸고 연결된 모든 노드를 스택에 삽입

---

🔸 end 🔸

• dfs로 풀려다가 bfs가 더 깔끔한 것 같아 전향하였다.
• dfs도 연습할 수 있는 문제를 풀어야겠다.