촌수계산-2644

dfs 풀이

package dfs;

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

public class 촌수계산 {
    public static List<Integer>[] person; // 받을 사람
    public static int count; // 카운트
    public static int result = -1; // 카운트
    public static boolean[] visited; // 방문 처리
    public static int end;

    public static void solution(int[][] graph, int start, int n) {
        person = new ArrayList[n + 1];

        for (int i = 0; i < person.length; i++) {
            person[i] = new ArrayList<>();
        }

        for (int[] edge : graph) {
            person[edge[0]].add(edge[1]);
            person[edge[1]].add(edge[0]);
        }

//        System.out.println(Arrays.toString(person));
        visited = new boolean[n + 1];

        dfs(start);
    }

    public static void dfs(int start) {
        visited[start] = true; // 방문 후 true
        if (start == end) {
            result = count;
            return;
        }

        for (int n : person[start]) {
            // 방문하지 않았다면
            if(!visited[n]) {
                count++;
                dfs(n);
                count--;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 사람 수
        StringTokenizer st = new StringTokenizer(br.readLine());

        int p2 = Integer.parseInt(st.nextToken()); // 사람1
        int p1 = Integer.parseInt(st.nextToken()); // 사람2
        end = p2;

        int m = Integer.parseInt(br.readLine()); // 간선
        int[][] graph = new int[m + 1][2];

        for (int i = 1; i < m + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        /*for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < 2; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();

        }*/


        solution(graph, p1, n);

        System.out.println(result);
    }
}

---

bfs 풀이

• 2025.03.02
  BFS로 재풀이 했습니다.(dfs로도 한번 더 했습니다)

  Node라는 정적 내부 클래스 선언해서 값을 받을 수 있는 cnt, value을 필드에 선언을 한 다음에 int대신 Node클래스를 사용하는 방식입니다.

  for문 안에서 인접노드가 돌며 for문 위에 외부에 있는 전 노드의 cnt를 기억해둔 다음 +을 해주는 방식입니다.

package dfs.Day250227;

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

public class Day04_촌수계산_BFS_DFS {
    static List<Node>[] adjList;
    static boolean[] visited;
    static int n;
    static Node endNode;
    static int result = -1;

    public static class Node {
        public int cnt;
        public int value;

        public Node(int value, int cnt) {
            this.value = value;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "|" + value + ", " + cnt + "|";
        }
    }

    public static void dfs(Node startNode) {
        visited[startNode.value] = true;
        if (startNode.value == endNode.value) {
            result = startNode.cnt;
            return; 
        }

        for (Node n : adjList[startNode.value]) {

            if (!visited[n.value]) {
                dfs(new Node(n.value, startNode.cnt + 1));
            }

        }

    }

    public static void bfs(Node startNode) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.add(startNode);
        visited[startNode.value] = true;
        
        while (!queue.isEmpty()) {
            Node poll = queue.poll();

            if (poll.value == endNode.value) {
                result = poll.cnt;
            }

            for (Node node : adjList[poll.value]) {
                if (!visited[node.value]) {
                    visited[node.value] = true;
                    queue.add(new Node(node.value, poll.cnt + 1));
                }
            }
        }

    }

    public static void solution(int[][] graph, Node startNode) {
        adjList = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            adjList[i] = new ArrayList<>();
        }


        // 인접리스트 생성
        for (int[] i : graph) {
            adjList[i[0]].add(new Node(i[1], 0));
            adjList[i[1]].add(new Node(i[0], 0));
        }

		bfs(startNode);
        // dfs(startNode);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Node startNode = new Node(Integer.parseInt(st.nextToken()), 0);
        endNode = new Node(Integer.parseInt(st.nextToken()), 0);
        int m = Integer.parseInt(br.readLine());

        int[][] graph = new int[m][2];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph[i][0] = Integer.parseInt(st.nextToken());
            graph[i][1] = Integer.parseInt(st.nextToken());
        }

        solution(graph, startNode);
        System.out.println(result);
    }
}

문제

촌수계산이라는 BFS/DFS 알고리즘을 풀었습니다.

간단히 말하면 사람들의 관계를 그래프로 주고 촌수를 계산해야되는 두 사람을 줍니다.
그 두 사람의 촌수계산을 구하는 문제였습니다.

처음에 접근 자체는 나쁘지 않았습니다.
DFS 재귀에 들어올 때는 count++, 재귀를 빠져나올 때는 count--하는 방식을 사용하여 원하는 촌수를 만나면 현재까지 count한 촌수를 result 값에 넣고 빠져나가는 방식이었습니다.

결과

한시간이 지나서 결국 답지를 보았는데, 자꾸 DFS에서 for문이 돌 때 값이 0이 나와서 오류를 찾지 못했습니다. 1시간이 지나고 답지를 보았더니 두 가지 문제점이 발견되었습니다.

1. result를 -1로 선언
   result를 처음부터 -1로 선언하여 촌수를 찾지 못했을 때 -1을 출력하는 방식을 사용하지 않았습니다. (이 부분은 크게 중요하지 않았습니다.)

2. 양방향 그래프로 선언 하지 않은 점
   지금 보니 당연히 양방향으로 해야 하는데, 왜 그런지 모르겠습니다.
   단방향 그래프로 접근하려고 시도 중이었지만, 단방향으로 하니 초반 노드가 빈 배열이 뜨는 것이었습니다. 아무렇게나 노드를 접근했을 때 접근하게 시도했어야 했습니다.