[BOJ] 2644. 촌수계산

 

문제

 

 

 

입력 예제

 

 

 

 

 

문제 풀이

 

 

입력 예제를 바탕으로 그래프화 해본 결과, 최단 경로를 구하는 방식이나 깊이 우선 탐색을 이용하는 방법으로 풀이가 가능하다는 생각이 들었다. DFS & BFS 둘 다로 풀이할 수 있는 문제이므로 두 알고리즘을 각각 적용하여 풀이해보기로 했다.

 

 

 

BFS

 

 

위 그래프의 인접행렬과 노드 간 연결 관계(양방향)를 테이블로 표현해보았다.

추가) 아래 그림에서는 인접리스트라고 적었지만 구현은 인접행렬 방식으로 되어 있습니다.

 

인접행렬과 인접리스트의 차이가 궁금하다면 맨 아래 링크된 글을 참고 바랍니다.

 

 

 

 

방문 배열값 업데이트 과정은 다음과 같다.

 

 

 

import java.util.*;

public class BOJ2644 {

    static int n, m, start, end;
    static int[][] arr;
    static int[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());
        visited = new int[n+1];

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 서로 양방향으로 연결되어 있음을 의미
            arr[x][y] = 1;
            arr[y][x] = 1;
        }

        BFS(start);

        System.out.println(visited[end] == 0 ? -1 : visited[end]);
    }

    public static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<Integer>();

        // 시작점 큐에 삽입
        queue.add(index);

        System.out.println("start queue:" + queue.toString());

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            if (curr == end) break;
            for (int i=1; i<=n; i++) {
                // 방문 조건 : 현재 노드와 다음 노드가 연결된 상태이고 아직 방문하지 않은 상태일 때
                if (arr[curr][i] == 1 && visited[i] == 0) {
                    queue.add(i);
                    // i번째 배열값에 1씩 +하며 카운트
                    visited[i] = visited[curr] + 1;
                }
            }
        }
    }
}

 

 

 

DFS

 

위 문제를 DFS 방식으로도 풀이해보았다. BFS와 전체적인 틀은 같으나 queue를 사용하는 대신 재귀적인 탐색을 통해 결과값을 출력하는 형태이다.

 

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

public class BOJ2644_DFS {

    static int n, m, start, end, result = -1;
    static int[][] arr;
    static int[] visited;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());
        visited = new int[n + 1];

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 서로 양방향으로 연결되어 있음을 의미
            arr[x][y] = arr[y][x] = 1;
        }

        DFS(start, 0);
        System.out.println(result);
    }

    public static void DFS(int index, int cnt) {

        if (index == end) {
            result = cnt;
            return;
        }

        for (int i=1; i<=n; i++) {

            // 방문조건: start와 연결되어 있으면서 아직 방문하지 않은 상태
            if (arr[index][i] == 1 && visited[i] == 0) {
                // 방문 횟수 카운트 1씩 증가
                visited[i] = visited[i] + 1;

				// 촌수 관계 증가시키면서 다음 촌수로 이동
                DFS(i, cnt+1);
            }
        }
    }
}

 

 

위 코드의 탐색 순서를 보면 다음과 같이 탐색되는 것을 확인할 수 있다.

 

 

 

 

 

 

https://loosie.tistory.com/151

[알고리즘/ 그래프] DFS와 BFS 정리 (Java)