[프로그래머스, 자바, 1260번] DFS와 BFS

풀이

• 세상에 파이썬으로는 정말 엄청나게 간결하게 할 수 있는 코드인데
• 자바는 역시 코드가 엄청나게 길게 작성되는 것 같다.
• 우선 기본적인 알고리즘 해결 방법은 같다.
• 다만 for문 작성을 줄이고 최대한 stream을 사용해서 가독성을 늘리려고 하니깐
• 다양한 시도를 해보다가 늦게 되었는데
• 우선 새롭게 알게 된 것들에 대해 작성하자면
  1. 1. Collections.nCopies()에 두 번째 인자로 new ArrayList<Integer>() 을 넣고 돌리니
     1. 같은 주소값을 가지는 배열을 똑같이 추가해서 의도한 코드 구현이 안되었다.
     2. 그래서 IntStream.rangeCloesd() 로 원하는 크기의 배열을 만든 다음
     3. mapToObj에서 ArrayList<Integer> 객체를 lambda 형식으로 새롭게 만들고
     4. Collections 타입이기에 .collect(Collectors.toList())로 배열화 하여 해결
     5. 여기서 IntStream의 range와 rangeCloesd는 2 번째 인자값까지 포함할 건지를 의미
  2. 2. 2차원 배열의 각 인덱스 별 배열을 정렬하고자 할 경우와 내림차순 정렬하는 방법
     1. 우선 그냥 오름차순 정렬의 경우 for문을 사용해서 정렬할 수도 있지만
     2. forEach를 사용하면 ArrayList는 Collections 이기에
        1. li.forEach(Collections::sort) 하면 된다
     3. 여기서 내림차순 정렬은 단순히 reverse만 하면 정렬이 안된 상태로 거꾸로 만드는 것이기에
        1. li.forEach(arr->arr.sort(Comparator.reverseOrder()) 처럼
        2. sort() 메서드 안에 Comparator.reverseOrder() 를 사용하여 거꾸로 만들어줘야한다.
  3. 3. 2차원, 3차원의 특정 인덱스 값 추가
     1. 처음에는 흠 어떻게 해야하지 했는데 엄청 간단하게 .get().add() 이렇게 이어서 나가면 됨
• 이후 따로 코드에 관련한 설명은 필요없을 만큼 단순한 문제라 끝내고
• 마지막으로 해당 문제는 양방향으로 연결된다는 것만 알면 문제 없을 듯. 

 

import java.io.*;
import java.util.*;
import java.util.stream.*;
public class _1260 {
    static List<Boolean> visit;
    static List<Integer> result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] NMV = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = NMV[0];
        int M = NMV[1];
        int V = NMV[2];


        // 노드 연결
        List<List<Integer>> li = IntStream.rangeClosed(0,N).mapToObj(ArrayList<Integer>::new).collect(Collectors.toList());
        for (int i=0; i<M; i++) {
            int[] node = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            li.get(node[0]).add(node[1]);
            li.get(node[1]).add(node[0]);
        }
        li.forEach(arr-> arr.sort(Comparator.reverseOrder()));

        // dfs
        visit = new ArrayList<>(Collections.nCopies(N+1,false));
        result = new ArrayList<>(N);
        Deque<Integer> stack = new ArrayDeque<>(){{
            add(V);
        }};

        while (!stack.isEmpty()) {
            int now = stack.pollLast();
            if (!visit.get(now)) {
                result.add(now);
                visit.set(now,true);
            }
            for (int num: li.get(now)) {
                if (!visit.get(num)) stack.add(num);
            }
        }
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));

        // bfs
        li.forEach(Collections::sort);

        visit = new ArrayList<>(Collections.nCopies(N+1,false));
        result = new ArrayList<>(N);

        Deque<Integer> queue = new ArrayDeque<>(){{
            add(V);
        }};
        visit.set(V,true);
        result.add(V);

        while (!queue.isEmpty()) {
            int now = queue.pollFirst();

            for (int num: li.get(now)) {
                if (!visit.get(num)) {
                    visit.set(num,true);
                    queue.add(num);
                    result.add(num);
                }
            }
        }
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}