https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 개요 어제 포스팅했던 트리의 지름과 똑같은 문항이다. input의 형식이 조금 바뀌어서 index와 관련해 생각할 부분이 늘어났지만 그 외의 풀이는 차이가 없다. 이전에 BFS로 문제를 해결했어서, 이번엔 DFS로 접근해봤는데 visit리스트의 리셋이나 변수들의 유효 범위 등 고려할 것들이 많아져 결국 포기. 추가로 우수 풀이 중 BFS/DFS가 아닌 괜찮은 접근의 풀이가 있어 소..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 개요 트리 알고리즘 문항이긴 하나, 해결법은 BFS다. 트리를 정리하는 자료구조로 보통 리스트나 딕셔너리가 사용되는 건 알고 있었는데, 문제별로 그 구조를 조정할 필요는 있을 듯하다. 사실 처음 문제 풀 때 꽤 어렵게 접근해서 쩔쩔매긴 했는데, BFS를 두번 진행한다는 식의 발상은 못했다 아이디어 - BFS를 이용하여 루트 노드(1)부터 탐색을 진행한다. 가장 큰 가중치를 갖는..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 트리 알고리즘이라고 쓰기는 했지만, DFS, BFS 문항 중 가장 기본 문제인 것 같다. 실버2에 랭크되어 있는 것에 비해 아직 숙련도가 많이 부족해서 입력값 정리, 알고리즘 전개 방식 등 다방면에서 많이 헷갈리더라. 지난번에 포스팅했던 내용과 큰 차이는 없지만 이렇게까지 기억이 안나는 걸 보면 복습이 확실히 중요한 듯싶다. 백준 티어 실버1으로 올랐다. 조금..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 본격적으로, BFS - DFS 문제들이 등장한다. 어떤 식으로 작동하는지는 책을 통해 공부한 바가 있지만, 실질적으로 구현해보지는 않아서 구글링을 통해 몇 번 연습한 뒤 문제 풀이에 임했다. 우선 느낀 점은 단순히 알고리즘을 구현하는 일과 그걸 직접 문제에 적용시키는 일은 정말 다르다는 점이다. 거의 3시간을 BFS, DFS에 쏟을 정도로 오래 걸리더라. 남의 코드를 직관적으로 이해하는 능력이 조금 부족해서 공부의 효율이 떨어지는 듯한다. 내가 구현해 본 BF..
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 어젯밤에 이진트리 알고리즘 구현 공부를 하다 자서, 감이 올라왔을 때 한 문제라도 풀어보는 게 좋을 것 같아 트리 알고리즘 중에 가장 쉬운 난이도를 골랐다. 확실히 구현 자체와 문제 풀이 간의 차이는 존재하더라. 노드 클래스와 트리 클래스를 정의해서 긴 호흡으로 끌고 가는 게 당연하다고 생각했는데, 생각보다 풀이는 단순하더라. # PYTHON CODE (1) import sys n = int..
