99클럽 코테 스터디 7일차 TIL [BFS]

- 오늘의 학습 키워드 : BFS 알고리즘

 

[문제 이름 : 노드사이의 거리 (백준 1240, G5)]
문제 url : https://www.acmicpc.net/problem/1240

내가 작성한 코드는 아래와 같다.

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

public class Main {

    static int n, m;
    static ArrayList<Node>[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        A = new ArrayList[n+1];

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

        for(int i=0; i<n-1; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            A[a].add(new Node(b, value));
            A[b].add(new Node(a, value));
        }
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            boolean[] visited = new boolean[n+1];

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(BFS(a, b, visited)).append("\n");
        }
        System.out.println(sb.toString());
    }

    static int BFS(int a, int b, boolean[] visited) {
        Queue<Node> queue = new LinkedList<>();
        visited[a] = true;
        queue.add(new Node(a, 0));

        while(!queue.isEmpty()) {
            Node cur = queue.poll();

            if(cur.end == b) {
                return cur.value;
            }

            for(Node next : A[cur.end]) {
                if(!visited[next.end]) {
                    visited[next.end] = true;
                    queue.add(new Node(next.end, cur.value + next.value));
                }
            }
        }

        return -1;
    }

    static class Node {
        int end;
        int value;

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

 

풀이 과정 (풀이 시간 : 20분)

처음에는 트리 문제라고 해서 루프노드부터 차례대로 배열에 넣는 형식인가 하고 문제를 봤는데, 그냥 DFS, BFS 문제였다. BFS로 푸니 문제가 바로 풀려서 별다른 리팩토링 없이 작성하였다.

1. 노드 두 개와 이에 대한 가중치를 입력 받고, ArrayList배열을 선언한 A에 값을 저장해준다.

2. Node라는 클래스를 활용하여, 도착 지점의 노드와 해당 지점과의 거리(value)를 저장한다.
3. m번 만큼 반복해야 하므로, 방문 배열을 저장하기 위한 visited 배열과 함께 bfs를 돌린다.

4. 처음 시작할 때는 거리가 0이므로, (시작 지점, 0)을 큐에 삽입 후, BFS를 수행한다. 이 과정을 반복하면서 도착 지점의 노드에 도달하면, 이때까지의 거리를 리턴해주고, 그게 아니라면 현재 가중치에서 이동할 노드의 가중치를 더해서 큐에 삽입해준다.

5. StringBuilder로 값을 저장해주고, 한 번에 출력한다.

내일은 목요일 면접에 대하여 스터디를 진행할 예정이다.