[알고리즘]백준 2644번 촌수계산(DFS와 BFS알고리즘)

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

테스트 케이스	결과
6 1 5 5 1 2 2 3 2 4 4 5 4 6	3

 

1. DFS 풀이법 (깊이 우선 탐색)

포인트
depth를 카운트 해야한다.
 

처음에 모든 노드의 수를 count하는 코드를 짜서 틀렸었다.
dfs[idx]에 count 정보가 함께 들어가도록 코드를 짜야한다.
dfs함수를 타는 횟수에 따라 count가 매번 증가하는 게 아니라서
다른 dfs함수가 먼저 돌았든 말든 상관없다!

import java.io.*;
import java.util.*;
public class Test2644 {
static int N,M,start,end;
static int answer = -1; //초기값 설정
static boolean[][] graph;
static boolean[] visited;

    public static void dfs(int idx, int count){
        visited[idx] = true; //dfs함수를 타는 순간 해당 idx는 방문했다는 것을 표시함.


        if(idx == end){ 
            answer = count;
        }

        for(int i = 1; i <= N; i++){
            if(visited[i]==false&&graph[idx][i]==true) {
            //조건 만족하면 dfs함수를 타고 count +1 해줌.
                    dfs(i,count+1);
            }
        }

    }
    
    public static void main(String[] args) throws IOException{
    //입출력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(br.readLine());

        //정보 채우기
        graph = new boolean[N+1][N+1];
        visited = new boolean[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());
            graph[x][y] = true;
            graph[y][x] = true;
        }

        //함수 호출
        dfs(start,0);

        //출력
        bw.write(String.valueOf(answer));

        br.close();
        bw.close();
    }
}

 
 

2. BFS 풀이법 ( 너비 우선 탐색 )

이 문제는 촌수(최단 거리)를 구하는 문제다.
BFS는 주어진 노드에서 시작하여 가장 가까운 이웃부터 방문하기 때문에 DFS보다 더 직관적이다.
 
포인트
- 큐는 FIFO(First In, First Out) 특징을 갖고있다.
poll()로 맨앞 요소를 뽑아내서 촌수 확인을 해야한다.
- 큐는 ArrayList보다 LinkedList를 사용해줘야한다. (시간복잡도 때문)

import java.io.*;
import java.util.*;

public class Test2644_bfs {
    // 전역 변수로 사람 수, 관계 수, 시작점, 종료점을 선언.
    static int N, M, start, end;
    static boolean[][] graph; // 2차원 배열을 통한 관계 표현.
    static boolean[] visited; // 재방문 방지

    public static int bfs() {
        Queue<Pair> queue = new LinkedList<>();
        // LinkedList를 사용해야 ArrayList사용할때보다 시간복잡도 줄일 수 있다.
        // L은 O(1) A는 O(n)
        queue.add(new Pair(start, 0)); // 시작점과 초기 촌수(0)을 큐에 삽입

        while (!queue.isEmpty()) {
            Pair current = queue.poll(); //맨앞요소 제거하고 current에 담아줌.

            if (current.idx == end) return current.count; // 종료점에 도달하면 촌수 반환

            for (int i = 1; i <= N; i++) {
                if (!visited[i] && graph[current.idx][i]) {
                    visited[i] = true;
                    queue.add(new Pair(i, current.count + 1)); // 방문한적 없고 연결되어있는 노드를 큐에 추가
                }
            }
        }

        return -1; // 경로가 없을 경우 -1 반환
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(br.readLine());
        graph = new boolean[N + 1][N + 1];
        visited = new boolean[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());
            graph[x][y] = graph[y][x] = true;
        }

        int answer = bfs();
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    // BFS에 사용될 Pair 클래스 (노드의 index와 해당 노드까지의 촌수를 저장)
    static class Pair {
        int idx, count;

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