트리

[백준] 1197 최소 스패닝 트리 | MST(Prim) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 프림 알고리즘프림이 노드를 추가하는 방식이지만 결국은 간선의 가중치를 확인해야 하는데논리를 너무 노드에만 집중해서 생각했다. 생각을 열어두자~ [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제 1 1 음수 가중치 간선 존재, 양방향 가중치 절댓값 시간 제한 1초 메모리 제한 128MB  [개념]MST 구하는 법 크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것정점보다 간선 개수 범위가 더 커서 프림으로 짜보자  구상 1 간선 입력받아 리스트..

[백준] 14675 단절점과 단절선 | Sil1 | 트리 Pythonhttps://www.acmicpc.net/problem/14675 구상유형 : 그래프(트리만 입력되는 경우) 단절점, 단절선 개념  [문제해석]주어진 트리에서 각 노드, 간선이 단절점, 단절선인지 묻는 질문에 답 출력질의 내용 t=1 일 때 : k번 정점이 단절점인가?t=2 일 때 : k번째로 입력받았던 간선이 단절선인가? 개념단절점, 단절선 : 특정 노드 또는 선을 제거했을 때 해당 그래프가 2개 이상으로 분리된다면 해당 노드 또는 선을 단절점 또는 단절선이라한다.DST(DFS Spanning Tree)를 활용해 단절점, 단절선을 판단할 수 있다.트리 : 모든 노드가 연결되어있는, 사이클 없는 그래프-> 사이클이 없고 모든 노드가 연..

[백준] 1991 트리 순회 | Sil1 | 그래프,트리 Pythonhttps://www.acmicpc.net/problem/1991 구상유형 : 트리 (dfs) [문제 해석]주어진 트리를 전위, 중위, 후위 순회한 순으로 각각 출력항상 A가 루트노드임시간제한 : 2초순회 방식전위 순회 : 루트 → 왼쪽 → 오른쪽 자식 순으로 방문중위 순회 : 왼쪽 → 루트 → 오른쪽후위 순회 : 왼쪽 → 오른쪽 → 루트 구상일단 트리를 입력받고.. 루트가 누군지 알려주니까 거기서부터 찾아가자세가지 순회 모두 현재 노드 기준으로 우선순위 먼저인 것부터 재귀호출 돌게 하고, 루트노드를 탐색하는 순서에 현재노드를 답에 추가해주면 된다. 트러블 슈팅순회방식 이해 한번에 못해서 몇번을 시뮬함 ㅎ 코드# v1 : 트리 (dfs)..

[백준] 14675 단절점과 단절선 | Sil1 | 그래프,트리 Pythonhttps://www.acmicpc.net/problem/14675  구상**주의**이 문제는 입력으로 트리만 들어오는데, 이 글은 트리가 아닌 그래프가 입력되어도 풀 수 있게 짠 풀이입니다.트리만 입력되는 경우에는 더 쉽게 풀 수 있으니 이렇게 안풀어도 됨!!!!!더 쉬운 풀이는 따로 글 쓰겠습니다  유형 : 그래프(트리)단절점, 단절선 개념 단절점 단절선 찾기 로직 이해하느라 한참걸렸다.. 나 이런거에 약해-> 아니 이문제는 이렇게 안풀어도 되는 문제입니다...ㅎㅎ... 트리만 주어지는 문제인데 나는 트리 아닌 그래프가 와도 되는 풀이로 풀고있던 거였다 어쩐지 어렵드라;;;; 트리만 입력될 때 쓸 수 있는 풀이로도 다시 풀어서..