• Home

My Codegate

  • Home

백준 18352 특정 거리의 도시 찾기 자바 문제풀이

2024/01/16 Posted by Codegate Java No Comments

문제 링크

문제 내용은 입력으로 그래프 구조를 받아, 시작 위치에서부터 지정된 횟수 만큼 이동했을 때 도달할 수 있는 정점을 오름차순으로 출력해주면 되는데, 없을 경우에는 -1을 출력한다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeSet;

public class Main {

  static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
  static int[] visited;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    for (int i = 0; i < split[1]; i++) {
      int[] edge = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
      graph.putIfAbsent(edge[0], new ArrayList<>());
      graph.putIfAbsent(edge[1], new ArrayList<>());
      graph.get(edge[0]).add(edge[1]);
    }

    visited = new int[split[0] + 1];
    Arrays.fill(visited, -1);
    bfs(split[3], split[2]);
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 1; i < visited.length; i++) {
      if (visited[i] == split[2]) {
        set.add(i);
      }
    }

    if (set.isEmpty()) {
      System.out.println(-1);
    } else {
      for (Integer integer : set) {
        System.out.println(integer);
      }
    }
  }

  public static void bfs(int start, int min) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = 0;

    while (!queue.isEmpty()) {
      Integer poll = queue.poll();
      for (int neighbor : graph.get(poll)) {
        if (visited[neighbor] == -1) {
          visited[neighbor] = visited[poll] + 1;
          queue.add(neighbor);
        }
      }
    }
  }

}

문제를 풀어보자면, 먼저 그래프를 구성해주되 단방향이므로 양방향 처리하지 않도록 주의하고 BFS를 돌려줘야 하는데 visited 배열에 방문 순서를 모두 기록해준 후

BFS가 끝나면 최단 거리에 해당하는 항목들을 모두 넣어줘야 하는데 TreeSet을 사용하면 자동 오름차순 정렬이므로 정렬할 필요가 없다.

이후 TreeSet이 비었으면 -1을 출력하고 값이 있으면 차례대로 출력해주면 자동으로 오름차순 된 값만 나오게 된다

No Comments
0

Leave a Reply Cancel Reply

Introduction

My Codegate

Latest Posts

  • Google Search Console API 연동방법
  • 인텔리제이 Gradle Dependency 최신 버전 보는 방법
  • Wallet-Tracker 개발일지
  • Moralis API 자바로 호출방법
  • IntelliJ Commit 후 Push 따로 하는 방법

Categories

  • My Project (4)
  • Java (42)
  • Algorithm (161)
    • Java (152)
    • Algorithm Knowledge (3)
    • Algorithm site usage (6)
  • Vue.js (1)
  • Spring (4)
  • Docker (2)
  • IntelliJ (20)
  • Uncategorized (7)

Recent Comments

  • Codegate on Hello world!
  • A WordPress Commenter on Hello world!

© 2025 — mycodegate.com

Prev Next