[백준, 자바, 18352번] 특정 거리의 도시 찾기

풀이

• 흠 원래 코드를 좀 간결하게 하고자 IntStream을 종종 사용했는데, 주의해야할 듯하다..
  • 이것 땜에 메모리 초과로 한참을 고생했네,,,
• 그리고 기존 비용 관련 문제의 경우 현재 비용을 함께 전달하여 해결하곤 했는데,
• dp를 사용해서 현재 좌표에 해당하는 인덱스의 값을 활용하는 방법도 좋다고 생각.
  • 이건 다른 사람들 코드를 보고 확인
  • 그런데 이렇게 하니까 훨씬 코드가 더 깔끔해져서 좋은거 같음.
  • 1번 풀이 참조

 

// 1번 풀이

import java.io.*;
import java.util.*;
public class _18352 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        List<List<Integer>> citys = new ArrayList<>();
        for (int i=0; i<=N; i++) citys.add(new ArrayList<>());
        int[] cost = new int[N+1];
        Arrays.fill(cost,-1);

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            citys.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
        }

        Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(X));
        cost[X] = 0;

        List<Integer> result = new ArrayList<>();

        while (!dq.isEmpty()) {
            int now = dq.pollFirst();
            if (cost[now]==K) result.add(now);
            else {
                for (Integer val: citys.get(now)) {
                    if (cost[val]==-1 && cost[now]+1<=K) {
                        cost[val] = cost[now]+1;
                        dq.add(val);
                    }
                }
            }
        }
        if (result.isEmpty()) System.out.println(-1);
        else {
            Collections.sort(result);
            for (int num: result) bw.write(num+"\n");
            bw.flush();
        }
    }
}

 

// 2번 풀이

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        List<List<Integer>> citys = new ArrayList<>();
        for (int i=0; i<=N; i++) citys.add(new ArrayList<>());
        long[] cost = IntStream.rangeClosed(0,N).mapToLong(i->300000L*N).toArray();
        boolean[] visit = new boolean[N+1];
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            citys.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
        }
        Deque<List<Integer>> dq = new ArrayDeque<>(Arrays.asList(new ArrayList<>(Arrays.asList(X,0))));
        visit[X] = true;
        Set<Integer> s_li = new HashSet<>();
        while (!dq.isEmpty()) {
            List<Integer> li = dq.pollFirst();
            if (li.get(1)==K && cost[li.get(0)]==K) s_li.add(li.get(0));
            else {
                for (Integer val: citys.get(li.get(0))) {
                    if (!visit[val] && cost[val]>li.get(1)+1 && li.get(1)+1<=K) {
                        cost[val] = li.get(1)+1;
                        visit[val] = true;
                        dq.add(new ArrayList<>(Arrays.asList(val,li.get(1)+1)));
                    }
                }
            }
        }
        if (s_li.isEmpty()) System.out.println(-1);
        else {
            List<Integer> result = new ArrayList<>(s_li);
            Collections.sort(result);
            for (int num: result) bw.write(num+"\n");
            bw.flush();
        }
    }
}