99클럽 코테 스터디 7일차 TIL (챌린저): [백준][Java] 1240 노드사이의 거리 - 골드5

 

문제 보기

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

 

 

풀이

BFS로 문제를 풀었다.

시작 노드부터 현재 노드까지의 길이가 얼만지 계속 기록하고

현재 노드가 입력된 노드에 도달할 시

거리를 출력하였다.

 

  while (!queue.isEmpty()) {
    int[] node = queue.poll();
    if(node[0] == endNode) {
      bw.write(node[1] + "\n");
      break;
    }

    for(int j = 0; j < list[node[0]].size(); j++) {
      if(!visited[list[node[0]].get(j)[0]]) {
        visited[list[node[0]].get(j)[0]] = true;
        queue.add(new int[]{list[node[0]].get(j)[0], node[1] + list[node[0]].get(j)[1]});
      }
    }
  }

BFS를 돌리는 부분인데 특별한 부분은 없다.

 

나는 Java에서 여러 변수를 한 곳에 담을 필요가 있을 때 같은 타입일 경우 주로 배열을 사용한다.

클래스로 만드는 건 귀찮아서 그렇다.

편한 쪽으로 하면 좋을 것 같다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");
    int N = Integer.parseInt(inputs[0]);
    int M = Integer.parseInt(inputs[1]);
    List<int[]>[] list = new ArrayList[N+1];
    for(int i = 1; i <= N; i++){
      list[i] = new ArrayList<>();
    }
    for (int i = 0; i < N - 1; i++) {
      inputs = br.readLine().split(" ");
      list[Integer.parseInt(inputs[0])].add(new int[]{Integer.parseInt(inputs[1]), Integer.parseInt(inputs[2])});
      list[Integer.parseInt(inputs[1])].add(new int[]{Integer.parseInt(inputs[0]), Integer.parseInt(inputs[2])});
    }

    for (int i = 0; i < M; i++) {
      inputs = br.readLine().split(" ");
      int startNode = Integer.parseInt(inputs[0]);
      int endNode = Integer.parseInt(inputs[1]);
      boolean[] visited = new boolean[N + 1];
      visited[startNode] = true;

      Queue<int[]> queue = new LinkedList<>();
      for(int j = 0; j < list[startNode].size(); j++) {
        queue.add(list[startNode].get(j));
      }

      while (!queue.isEmpty()) {
        int[] node = queue.poll();
        if(node[0] == endNode) {
          bw.write(node[1] + "\n");
          break;
        }

        for(int j = 0; j < list[node[0]].size(); j++) {
          if(!visited[list[node[0]].get(j)[0]]) {
            visited[list[node[0]].get(j)[0]] = true;
            queue.add(new int[]{list[node[0]].get(j)[0], node[1] + list[node[0]].get(j)[1]});
          }
        }
      }
    }

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/1240.%E2%80%85%EB%85%B8%EB%93%9C%EC%82%AC%EC%9D%B4%EC%9D%98%E2%80%85%EA%B1%B0%EB%A6%AC

CodingTest_AutoSave/백준/Gold/1240. 노드사이의 거리 at main · MetroDefro/CodingTest_AutoSave