백준 15805 트리 나라 관광 가이드

백준 15805 트리 나라 관광 가이드

---

오늘은 트리 구조 문제를 풀어보았다. 이거도 사실 dfs, bfs 를 사용할 필요가 없는 문제라고 생각해 사용하지 않았다.
핵심 부분은 다음과 같다 .

        for (int i = 1; i < n; i++) {
            if (visited[table[i]] != 0) {       //이미 위에서 방문한거 -> 말단 노드까지 갔다가 돌아오는 중,  그냥 continue
                continue;
            }
            if (visited[table[i]] == 0) {       // 지금 순회하며 첫방문, 윗 노드가 부모 노드임을 저장하고 방문 표시 해주면 됨.
                visited[table[i]] = 1;
                parents[table[i]] = table[i-1];
                max_val = Math.max(max_val, table[i]); //도시가 몇개 있는지 알려면 가장 큰 도시번호가 뭔지 알면 되니까
            }
        }

주어진 순서가 사실 dfs 순으로 온 것이기 때문에 지금 보고 있는 값 보다 하나 더 먼저 온 값이 부모란 사실을 알 수 있다.

다만, 만약 n 의 부모를 찾기위해 n-1 값을 보았을 때 n-1 이 이미 방문한 노드라면? 그 뜻은 지금의 과정이
이미 말단 노드까지 진행 후 돌아오는 중이란 걸 알 수 있는 것이다. 때문에 코드를 저렇게 작성해주었다.

하나 더

• max_val = Math.max(max_val, table[0]); // 첫번째 시작 도시가 제일 클 수도 있기 때문에.

100퍼센트 까지 찍고 틀렸습니다가 나온다면 이는 맨 첫 노드 값을 max 비교에 포함시키지 않아 노드 개수를 구하는데 문제를 일으켜서 그런 것이다.

이렇게 말고 정말 좋은 방법들이 많을 것 같아서 좀 아쉽다.