트리 필수 테크닉3 - 모든 정점들 각각 가장 먼 거리를 2번의 DFS로 구하는 방법
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
1. 문제 19542번: 전단지 돌리기 (acmicpc.net) 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 2. 풀이 트리로 구성된 그래프에서 모든 노드에 전단지를 돌려야하는데, 현재 노드에서 거리가 D이하인 모든 노드에 전단지를 한번에 돌릴 수 있다고 한다 트리 구조이기 때문에 부모 > 자식으로 내려가면서 각 노드마다 가장 먼 자식 노드까지의 거리를 안다면, 어디 노드까지만 방문해도 되는지를 파악할 수 있을 것이다. 10만개의 노드가 있어서 한번의 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..
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를 하면서 이동한..
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..
1. 문제1 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 풀이 A는 B의 친구이다 B는 C의 친구이다 C는 D의 친구이다 D는 E의 친구이다 이 말은 무슨말일까? A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말 주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것 깊이가 4이면 1을 return하고.. 깊이가 4가 아니면.. 탐색을 수행 현재 방문하는 점 x에 대한 방문처리 visited[x] = 1 x와 연결된 점 graph[x]에서 순회해..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
