lee-soo 님의 블로그

https://www.acmicpc.net/problem/1167 이 문제에 대해 간단히 설명하자면 여러개의 노드가 있을때, 한 노드와 또 다른 노드 사이의 거리가 제일 멀 때의 거리를 구하라그게 지름이고 이것이다. 예를들어 이렇게 노드가 있으면? 가장 긴 거리는3+2+6 =11이다 그래서 내가 먼저 처음에 생각한건 "무조건 거리를 잴 때는, 연결된 노드가 1개밖에 없는 경우이다"라고 생각해서 조건문으로 자식이 한개인 경우를 걸러낸 후,그 노드들에 대해 dfs를 통해 distance들을 알아내고max를 지정해줬었다 #include #include #include #include using namespace std;bool visited[100001];bool visited_2[100001];vector..

https://www.acmicpc.net/problem/11725 해당 문제는 루트를 1이라고 할 때, 노드 2번부터 n번까지 그의 부모 노드를 출력하면 되는 문제다 예를들어 입력된 예제를 보면 이런 형식으로 되어있고 2번노드의 부모는 43번은 64번은 15번은 36번은 17번은 4이므로461314가 나오게되는데 문제는 노드가 주어질 때, 그저 간선간의 정보만을 입력으로 줄 뿐 누가 부모노드인지 알려주지 않았다 하지만!우리는 1이 루트노드인걸 알았으니, 1로부터 시작한 탐색을 하면 되는데bfs로 하든 dfs로 하든 이건 상관없다 #include #include #include using namespace std;vectorint> v[100001];bool visited1[100001];int par..

https://www.acmicpc.net/problem/2250 호호..문제가 어려워 보이지만차근차근 읽으보면 입력은 부모 -> 왼쪽자식 -> 오른쪽자식로 이루어진다 자식이 없는 곳은 -1 로 표현한다 [TREE] 백준 1991번 트리의 순회(C++) [TREE] 백준 1991번 트리의 순회(C++)https://www.acmicpc.net/problem/1991 트리 순회 문제다. 아마 개발자를 목표로 하는 취준생이나, 대학생 3~4학년이라면 당연히 전위 중위 후위순위에 대한 알고리즘을 알고 있을 거다. 간단히 설명하자면,lee-soo.tistory.com사실 이 문제를 풀고온 후, 하나만 깨달으면 문제는 전혀 어렵지 않다. 이런 입력이 들어왔을 때 그림을 유심히 보자. 노드의 순서들이 어라. "트리..

https://www.acmicpc.net/problem/1991 트리 순회 문제다. 아마 개발자를 목표로 하는 취준생이나, 대학생 3~4학년이라면 당연히 전위 중위 후위순위에 대한 알고리즘을 알고 있을 거다. 간단히 설명하자면, 트리를 탐색할 때문제에 나온 것처럼 루트 , 왼쪽자식 ,오른쪽 자식순서대로 찾아볼거냐 왼쪽자식 루트 오른쪽 자식 or 왼쪽 오른쪽 루트 방식으로 찾아볼거냐에 대한 것이다. 그래서 전위순회를 한 경우에는 가장 먼저 A에서 시작하므로 루트 A를출력그 이후 왼쪽노드로 넘어가면B가 루트노드가되므로 B 출력그 이후 D 가...이렇게 반복하는 것이다 이런 문제는 재귀를 통해서 풀면 되는데 진입점에 따라 탐색 방식이 달라진다고 생각하면 된다. 예를들어 1.왼쪽노드 들어가기2.오른쪽노드 들..