18352_ 특정 거리의 도시 찾기

사용 알고리즘: 다익스트라(가중치가 다 똑같아서 쉬운 버전), 인접리스트, 큐(bfs처럼)

사용 언어: java

 

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

public class Main_18352_특정거리도시찾기 { //모든 도로의 거리는 1이다....(인접리스트에서 가중치 따로 저장할 필요x)
    static int n, m, k, x;
    static ArrayList<Integer>[] al ;

    static int[] dp; //시작점 x에서 가는 최소 거리를 저장할 배열
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        input();
        arrayInit();

        //한 바퀴 돌면서 dp 1차 갱신 (직행 도로 있는 곳은 inf대신에 직행값 넣기)
        //이 문제에선 가중치가 무조건 1이니까, 그냥 1 넣으면 됨
        dpUpdate1();

        //al 전체를 돌면서 dp 2차 갱신(이때는 건너건너 갈 수 있는 곳, 값 갱신 해주기)
        //근데 여기는 가중치가 다 똑같아서, 이어져만 있으면 됨.. 값 갱신은 한번밖에 없겠다...
        dpUpdate2();

//        System.out.println(Arrays.toString(dp));
        //답 찾기
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < dp.length; i++) {
            if(dp[i] == k) sb.append(i).append('\n');
        }
        if (sb.toString().isEmpty()) sb.append(-1);

        System.out.print(sb.toString());
    }

    private static void dpUpdate2() {
        Queue<Integer> q = new ArrayDeque();
        q.offer(x);

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : al[cur]) {
                if(!visited[next] ) {
                    q.offer(next);
                    visited[next] = true;
                    if( dp[next] == Integer.MAX_VALUE ){
//                        System.out.println(next+" "+cur+" "+dp[cur]);
                        dp[next] = dp[cur]+1; //++을 왜 썼니
                    }
                }
            }

        }
    }

    private static void dpUpdate1() {
        for (int i = 0; i < al[x].size(); i++) {
            dp[al[x].get(i)] = 1;
        }
    }

    private static void arrayInit() {
        dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = dp[x] = 0;

        visited = new boolean[n+1];
        visited[x] = true;
    }

    private static void input() 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());

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

        // 에구구ㅜㄱ
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            al[start].add(end);
        }

    }
}

 

 

다익스트라 - 플로이드워셜 - 크루스칼 - 벨만포드 형제들 중에 플로이드워셜 빼고 다 까먹어서

연습해본 문제 

 

개념 자체는 인접행렬로 알고 있어서, 인접 리스트+큐 활용 코드를 이해해야 했다.

다익스트라에서 인접행렬로 풀 수 있는 건 거의 안 나오나??

다익스트라에서 가장 쉬운 문제인데도 노드가 너무 많아 인접행렬을 쓸 수가 없었다..