99클럽 코테 스터디 10일차 TIL BFS(특정 거리의 도시 찾기)

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

 

오늘 문제는 단순 BFS지만 고려해야 하는 조건이 많은 문제였다,,

1. 양방향이 아닌 단방향 그래프

2. 방문 가능한 도시를 오름차순으로 출력 -> pq에 넣어서 출력했다.

3. 방문 가능한 도시가 0이면 -1 출력 -> 도시 방문 여부를 flag로 검사했다.

 

요 3개 조건만 잘 적용하면 되는 문제였는데, 난 여기에 방문 조건을 잘못 걸어서 출력초과와 틀렸습니다를 계속 받았다,,

** 고려하지 못했던 부분

1. 거리가 K를 넘어가면 q에 넣을 필요가 없다.

2. q에 안넣어도 방문 처리는 해줘야 한다!!!

package STUDY.Week02;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Day10_BOJ_18352_특정거리의도시찾기 {

    static class Point{
        int x, dis;
        Point(int x, int dis){
            this.x = x;
            this.dis = dis;
        }
    }

    static int n, m, k, x;
    static List<Integer>[] list;
    static PriorityQueue<Integer> pq;

    public static void bfs(){
        boolean[] visited = new boolean[n+1];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, 0));
        visited[x] = true;
        boolean flag = false;
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0; i<list[p.x].size(); i++){
                int nx = list[p.x].get(i);
                int ndis = p.dis + 1;
                if(visited[nx]) continue;
                // 최단 거리가 K면 저장하고 q에 넣지 않음.
                if(ndis == k) {
                    flag = true;
                    pq.add(nx);
                }
                // 아직 거리가 K 이하면 q에 넣음.
                else q.add(new Point(nx, ndis));
                // 모든 경우 다 방문처리
                visited[nx] = true;
            }
        }
        // 최단 거리 K로 도달할 수 있는 도시가 없는 경우
        if(!flag) pq.add(-1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        pq = new PriorityQueue<>();
        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];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
        }
        bfs();
        while(!pq.isEmpty()){
            System.out.println(pq.poll());
        }
    }
}

 

정답을 향한 눈물의 똥꼬쇼