[백준/JAVA] 18352번: 특정 거리의 도시 찾기

🔺 문제

18352번: 특정 거리의 도시 찾기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K ,X;
    static List<Integer> answer;    // 정답 리스트
    static ArrayList<Integer>[] A;  // 인접 리스트
    static int[] visited;           // 방문 배열
    
    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());   // 도로 개수
        K = Integer.parseInt(st.nextToken());   // 거리 정보
        X = Integer.parseInt(st.nextToken());   // 출발 도시 번호
        
        answer = new ArrayList<>(); // 정답 리스트
        
        // 인접 리스트의 각 ArrayList 초기화
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<Integer>();
        }
        
        // 인접 리스트 채우기
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            
            A[S].add(E);
        }
        
        // 방문 배열 초기화
        visited = new int[N + 1];
        for(int i = 0 ; i <= N ; i++) {
            visited[i] = -1;
        }
        
        BFS(X);
        
        for(int i = 0 ; i <= N ; i++) {
            if(visited[i] == K) {
                answer.add(i);
            }
        }
        
        if(answer.isEmpty()) {
            System.out.println(-1);
        }
        else {
            Collections.sort(answer);
            for(int a : answer) {
                System.out.println(a);
            }
        }
    }
    
 
    // BFS
    public static void BFS(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        visited[node]++;    // 현재 노드 방문 기록
        
        while(!q.isEmpty()) {
            int now_node = q.poll();
            
            for(int i : A[now_node]) {
                if(visited[i] == -1) {
                    visited[i] = visited[now_node] + 1;    // 이전 노드 방문 노드 거리 + 1
                    q.add(i);    // 큐에 인접 노드 삽입
                }
            }
        }  
    }
}

✅ 해결 아이디어
✔ BFS (∵ 최단 거리 탐색)
- 가중치 없는 인접 리스트 활용

 

💥 유의사항

• 방문 배열 내의 모든 원소를 -1로 초기화하기!

 

---

🔺 다른 풀이들

- 다익스트라 알고리즘을 사용하셨다.

백준 18352번 특정 거리의 도시 찾기 Java

[알고리즘] 백준 18352 특정 거리의 도시 찾기 -최단경로, 다익스트라- 자바

 

 

- boolean 활용

[BOJ] 18352 특정 거리의 도시 찾기_JAVA

---

💬 느낀 점

정답 배열을 만드는 것,,을 잊지 말자...

BFS도 잊지 말자,,,

 

 

1회독	2회독	3회독	4회독	5회독
V	0621	240129

 

(+ 230621 2회독)

방문 배열을 모두 -1로 초기화하는 것을 놓쳐서 틀림..ㅠ

그리고 전에 푼 거랑 비교해보니까

코드 길이는 짧은데 메모리, 시간은 더 많이 썼다..

 

그냥 리스트에 정답 원소 추가하고,

정렬하고 출력하는 게 은근 메모리랑 시간을 크게 먹지 않나보다..

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static ArrayList<Integer>[] A;    // 인접 리스트
    static int[] visited;             // 방문 배열
 
    static int N, M, K, X;
    static StringBuilder sb = new StringBuilder();
    
    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());   // 도로 개수
        K = Integer.parseInt(st.nextToken());   // 거리 정보
        X = Integer.parseInt(st.nextToken());   // 출발 도시 번호
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // 🔔 방문 배열, -1로 초기화 🔔
        visited = new int[N + 1];
        for(int i = 0 ; i <= N ; i++) {
            visited[i] = -1;
        }
        
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);
        }
        
        bfs(X);
        
        int answer = -1;
        for(int i = 0 ; i <= N ; i++) {
            if(visited[i] == K) {
                answer = i;
                sb.append(answer).append("\n");
            }
        }
        System.out.println(answer == -1 ? -1 : sb);
    }
    
    static void bfs(int num) {
        visited[num]++;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
                
        while(!queue.isEmpty()) {
            int now = queue.poll();
                    
            for(int next : A[now]) {
                if(visited[next] == -1) {
                    visited[next] = visited[now] + 1;
                    queue.add(next);
                }
            }
        }
    }
}

 

 

 

(+240129 3회독)

다 까먹다ㅎㅎ다익스트라 복습하자~~

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M,K,X;
    static List<Integer>[] list;
    
    static Queue<Integer> q = new ArrayDeque<>();
    static int[] distance;  // 거리 정보 저장 겸 방문 표시 배열
    
    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());   // 도로 정보
        K = Integer.parseInt(st.nextToken());   // 거리 정보
        X = Integer.parseInt(st.nextToken());   // 출발 도시 번호
        
        list = new ArrayList[N + 1];
        distance = new int[N + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            list[i] = new ArrayList<>();
            distance[i] = -1;   // 거리 배열 모두 -1로 초기화
        }
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            
            list[A].add(B); // 단방향
        }
        
        bfs();
        
        StringBuilder sb = new StringBuilder();
        boolean chk = false;
        for(int i = 1 ; i <= N ; i++) {
            if(distance[i] == K) {
                sb.append(i).append("\n");
                chk = true;
            }
        }
        System.out.println(chk ? sb : -1);
    }
    
    private static void bfs() {
        distance[X] = 0;    // 시작점 거리는 0으로 설정
        q.add(X);
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : list[now]) {
                if(distance[next] == -1) {  // 방문하지 않았다면, 방문
                    distance[next] = distance[now] + 1;
                    q.add(next);
                }
            }
        }
    }
}