신년맞이 boj - day1

신년맞이 작심20일 boj 챌린지

-하루에 정해진 분량만큼 문제 풀이(계획서 참고)

-각 문제별 간단 해결 방법+깃헙 링크 블로그 정리

---

1991 트리 순회

전: 루트->왼->오

중: 왼->루트->오

후: 왼->오->루트

 

전: 출력->왼 탐색->오 탐색

중: 왼 탐색->출력->오 탐색

후: 왼 탐색->오 탐색->출력

 

탐색은 어차피 같으므로 출력만 나누면 한 번에 한 함수에 때려넣을 수 있다

github.com/proqk/Algorithm/blob/master/Tree/1991%20%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C(3).cpp

 

 

2250 트리의 높이와 너비

1. 트리 만들기

2. 중위순회 돌면서 몇 번 노드가 몇 번째 레벨에 있는지 저장

3. 2번을 하면서 레벨마다 최소, 최대 값을 저장

4. 저장한 값을 보면서 최대-최소+1 중에 최댓값을 구하고 출력

 

왜 중위순회인가? 중위 순회를 하면 방문 순서 그대로가 각 노드의 x좌표가 되기 때문

그리고 문제에선 루트 노드가 무조건 1번 노드라는 말이 없어서 직접 찾아야 되는 점을 주의한다

 

풀고 보니까 2번은 굳이 필요없는 것 같다 그냥 3번을 순회 돌면서 할 거면..

 

github.com/proqk/Algorithm/blob/master/Tree/2250%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%86%92%EC%9D%B4%EC%99%80%20%EB%84%88%EB%B9%84.cpp

 

 

11725 트리의 부모 찾기

1. 트리를 만들기

2. 루트 1부터 dfs탐색으로 다음 노드가 있으면 다음 노드의 부모는 현재 노드로 저장

3. 부모 전체 출력

 

트리 탐색은 DFS/BFS 알고리즘으로 한다

이유: 트리는 사이클이 없는 그래프이기 때문에 임의의 두 정점 사이의 경로는 1개 -> 찾은 경로가 최단 경로

 

github.com/proqk/Algorithm/blob/master/Tree/11725%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%B6%80%EB%AA%A8%20%EC%B0%BE%EA%B8%B0(2).cpp

 

 

1167 트리의 지름

1. 트리 만들기

2. 어떤 정점부터 다른 모든 정점까지의 거리를 dfs탐색

3. 2번을 모든 정점에 대해 한 다음에 거리의 최댓값 출력

 

문제는 이렇게 하면 시간초과가 난다

이 문제는 모든 정점에서 거리를 구하는 접근이 아니라, 어떤 정점의 최대 거리 정점을 구하고, 그 정점의 최대 거리 정점 사이의 거리로 구하는 것이었다

이에 대한 증명은 blog.myungwoo.kr/112 이곳을 참고했다

 

1. 트리 만들기

2. 임의로 선택한 정점부터 다른 모든 정점까지의 거리를 dfs탐색

3. 2번에서 나온 거리 중에 가장 긴 거리인 정점에서부터 다른 모든 정점까지의 거리를 dfs탐색

4. 3번에서 나온 거리 중에 가장 긴 거리가 트리의 지름

 

이렇게 하면 총 2번 탐색으로 지름을 구할 수 있다

 

github.com/proqk/Algorithm/blob/master/Tree/1167%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84.cpp

 

 

9372 상근이의 여행

ㅡㅡ...

 

github.com/proqk/Algorithm/blob/master/Tree/9372%20%EC%83%81%EA%B7%BC%EC%9D%B4%EC%9D%98%20%EC%97%AC%ED%96%89.cpp