TIL 2022-06-11-토

1. 학습한 내용

백준 DFS 24480번 문제

• 문제
• 풀이

2. 알게 된 내용

ArrayList 정렬

// 오름차순으로 정렬        
Collections.sort(list);

// 내림차순으로 정렬        
Collections.sort(list, Collections.reverseOrder());

ArrayList는 Collections 안에 있는 sort함수로 정렬을 수행해야 한다.
내림차순 정렬은 뒤에 Collections.reverseOrder() 을 써주어야 한다.
출처 : https://hianna.tistory.com/569

잘못 생각했던 것

(다음에는 잘못 생각해서 실수하지 말자는 의미에서 적음...)
처음에 생각했던 것은, answer[] 배열에 각 인덱스를 출력순서로 보고, 각 출력 순서마다 무슨 노드인지를 넣는.. 것을 생각했다.
그래서

// 앞에서 index를 1로 두었음.

    static void dfs(int r) {
        answer[index++] = r; // 여기가 문제
        for (int node : list[r]) {
            if (!visited[node]) {
                visited[node] = true;
                dfs(node);
            }
        }
    }

이렇게 생각했었다. 주어진 예시는 잘 돌아갔지만 바로 틀렸습니다라고 떴다.

이렇게 틀린 이유는.. 내가 문제를 제대로 읽지 않아서였다. 문제에서 요구한 것은, 각각의 정점이 몇번째로 방문되는지를 출력하라고 했다! 따라서 내가 생각한 것은 틀렸었다.
따라서 이 부분은, index를 0으로 처음에 두고, 각 인덱스를 각각의 노드로 보고, 각 노드마다 몇 번째에 방문/호출되는지 인덱스값을 넣어야 하는 걸로 수정해야 한다!

// 앞에서 index를 0으로 두었음.
    static void dfs(int r) {
        answer[r] = ++index;  // 각각의 노드마다 방문 순서를 값으로 담도록 수정
        for (int node : list[r]) {
            if (!visited[node]) {
                visited[node] = true;
                dfs(node);
            }
        }
    }

문제를 잘 읽자..! 쪽팔리지만 다음에 같은 실수는 하지 말자는 마음으로 남겨둔다...

+) 이 사실을 깨닫게 된... 직접 만든 반례 하나 공유

반례 :
6 5 1
1 2
2 3
2 6
2 4
3 6

올바른 출력 :
1 2 6 3 0 4

로 출력되어야 한다.