백준 11725 트리의 부모 찾기

백준 11725 트리의 부모 찾기

---

오늘 문제는 트리의 부모 찾기로, 나같은 경우는 dfs를 이용해서 풀었다. 사실 저번에 공부할 때
트리 구조의 경우 dfs 에서 visited가 따로 필요 없고, 반드시 하나의 부모 노드에서 내려온 가지 이기 때문에 어쩌고
라는 내용을 공부했는데, 이번에 풀 때 적용이 안되어서 그냥 visited 를 하나 만들어서 이용했다.
어느 노드와 서로 연결 되어있는 노드들 중 적어도 하나는 반드시 visited된 상태일 것이고, 그 노드가 바로 현재 노드의 부모 노드인 것이다.
코드로 구현하는 것도 단순한 dfs 였다.

 while (!q.isEmpty()) {
            int cur = q.peek();
            visited[cur] = 1;
            q.remove();
            for (int i = 0; i < table.get(cur).size(); i++) {
                if (visited[table.get(cur).get(i)] != 1) {
                    answer[table.get(cur).get(i)] = cur;
                    q.add(table.get(cur).get(i));
                    visited[table.get(cur).get(i)] = 1;
                }
            }
        }