트리 탐색 테크닉2 - 현재 노드에서 가장 먼 자식 노드까지의 거리

1. 문제 19542번: 전단지 돌리기 (acmicpc.net) 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 2. 풀이 트리로 구성된 그래프에서 모든 노드에 전단지를 돌려야하는데, 현재 노드에서 거리가 D이하인 모든 노드에 전단지를 한번에 돌릴 수 있다고 한다 트리 구조이기 때문에 부모 > 자식으로 내려가면서 각 노드마다 가장 먼 자식 노드까지의 거리를 안다면, 어디 노드까지만 방문해도 되는지를 파악할 수 있을 것이다. 10만개의 노드가 있어서 한번의 DFS로 각 노드마다 가장 먼 자식 노드까지의 거리를 구해야..

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 15.
• textsms

트리 탐색 필수 테크닉 - 자식 노드로 내려가서 얻은 value를 부모 정점으로 value 보내는 DFS 테크닉

1. 문제 30414번: 투스타 춘배 (acmicpc.net) 30414번: 투스타 춘배 춘배 나라에는 $1$부터 $N$까지의 번호가 붙은 $N$개의 산, 그리고 두 산 사이를 이동할 수 있는 $N-1$개의 길이 있다. 게다가 임의의 두 산 사이를 항상 길을 통해 이동할 수 있다고 한다. 즉, 산을 www.acmicpc.net 2. 풀이 현재 산의 높이가 원하는 높이보다 작다면 흙을 차이만큼 구매하는게 좋고, 높다면 깎아내리는게 좋을 것이다. 근데 문제는 병사 1명이 u번에서 v번으로 내려갈때, 깎아내린 산 크기 X만큼을 가져가는데 u번에서 v번 경로가 아닌 다른 경로로 X만큼을 가져갈 수 없다는게 문제 트리 탐색은 DFS로 가능한데 v로 들어가기 전에 visited[v] = 1로 체크하고 나와서 vis..

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 13.
• textsms

트리에서 두 노드 사이 유일한 경로를 찾는 방법

1. 문제 30893번: 트리 게임 (acmicpc.net) 30893번: 트리 게임 첫째 줄에 정점의 개수 $N (2≤N≤100,000)$과 말의 시작 정점 $S$, 목표 정점 $E (1≤S, E≤N, S≠E)$가 주어집니다. 다음 $N-1$개의 줄에 걸쳐서 트리의 각 간선이 잇는 두 정점의 번호 $u, v (1≤u, v≤N, u≠v www.acmicpc.net 2. 풀이 트리니까, 출발 정점 S에서 도착 정점 E로 이동하는 경로는 유일하면서 반드시 존재한다. 이때, 선공은 어떻게든 S에서 E로 이동시킬려하고 후공은 E로 어떻게든 못가게 하는게 목적 여기서 한번 방문한 노드는 다시는 방문하지 못하니까, 이동 못하게 방해하는게 가능하다. 핵심은 S에서 E로 가는 경로를 찾아야하는데 DFS를 하면서 이동한..

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 5.
• textsms

트리 자료구조에 대한 개념과 트리에서의 다이나믹 프로그래밍 기본기(+트리를 만들지 않고 트리를 탐색하는 방법)

1. 그래프와 트리 그래프(graph)란 정점들과 정점 둘을 잇는 간선들로 이루어진 집합 위는 9개의 정점(원)과 10개의 간선(실선)들로 이루어진 그래프이다. 각 원의 내부에 쓰여 있는 숫자는 편의상 정점에 매긴 번호를 의미한다. 간선(edge)은 항상 두 정점을 잇게 된다. 그래프의 간선에는 가중치가 있을 수 있다. 특별한 언급이 없다면 간선의 가중치는 1로 간주할 수 있다. 가중치가 존재한다면, 예를 들어 1-3 간선의 가중치가 3이라면 1번 정점에서 3번 정점으로 가기 위해선 길이 3인 간선을 지나야한다고 표현한다. 그래프의 간선에는 방향성이 있을 수 있다. 예를 들어 1번 정점과 3번 정점사이 놓인 1-3 간선의 경우 1 > 3 또는 3 > 1 방향성을 가지는 것이 가능하다. 방향성 간선을 갖고..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 11. 29.
• textsms

DFS 2번으로 트리의 지름을 구하는 방법

1. 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이1 트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이 모든 경로가 유일하다. 가장 길이가 긴 경로를 트리의 지름이라고 정의했는데.. 어쨌든 가장 길이가 긴 경로라면 결국 리프 노드와 리프 노드 사이 거리가 가장 길이가 긴 경로이다. 루트 노드가 1번 노드이고 (부모, 자식)으로 입력이 주어지니까 부모 노드 모두 표시해두면 표시가 안된 노드는 어떤 노드의 부모가 아니니까..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 11. 28.
• textsms

DFS도 재귀보다는 반복문으로 구현 연습하기1

1. 문제 1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 풀이1 기본적인 DFS문제긴한디 분명히 맞는데 시간초과에 애먹었다.. from sys import stdin def dfs(x,y,s): global answer for i in range(4): dx = x + d[i][0] dy = y + d[i][1] if dx >= 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 a..

• format_list_bulleted DFS BFS 정복기
• · 2023. 8. 19.
• textsms