DFS11 [백준] 20294번 - 트리의 기둥과 가지 (C++) 문제 및 풀이 문제) 백준 - DFS/트리 - 트리의 기둥과 가지 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net DFS를 통해서 기둥과 가지를 탐색합니다. 기둥의 기준은 이어진 노드가 단 하나여야 되므로 graph의 사이즈가 1인 노드가 이어질 때까지 탐색합니다. 기둥의 마지막 부분을 저장해 가장 긴 가지를 탐색해 출력합니다. C++ 소스코드).. 2022. 2. 22. [백준] 3584번 - 가장 가까운 공통 조상 (C++) 문제 및 풀이 문제) 백준 - 트리/DFS - 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net DFS를 통해 한 노드에 대하여 조상으로 올라가 트리를 순회하여 Set에 모든 조상을 저장합니다. 그 후, 공통 조상을 탐색할 다음 노드에 대하여 마찬가지로 트리를 순회합니다. 이때 탐색한 조상이 Set에 있을 경우, 그 조상을 반환하여 출력합니다. C++ 소스코드) Full Code) ht.. 2022. 2. 19. [백준] 21937번 - 작업 (C++) 문제 및 풀이 문제) 백준 - DFS - 작업 https://www.acmicpc.net/problem/21937 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 깊이 우선 탐색을 통해 먼저 끝내야 할 작업의 수를 계산합니다. 그래프를 저장할 때 역순으로 저장하여 탐색을 진행합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21937_%EC%9E%91%EC%97%85.cpp GitHub - Cho.. 2022. 2. 15. [백준] 4803번 - 트리 (C++) 문제 및 풀이 문제) 백준 - DFS - 트리 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1번 노드부터 탐색하면서 트리의 개수를 계산합니다. 그래프에서 노드의 개수와 간선의 개수를 계산하여 cntEdge(i) / 2 == cntNode(i) - 1을 통해 트리 여부를 판별합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/480.. 2022. 2. 12. [백준] 16432번 - 떡장수와 호랑이 (C++) 문제 및 풀이 문제) 백준 - DFS - 떡장수와 호랑이 https://www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net N일에 팔 수 있는 떡 K를 Bool 형태의 배열에 T[N][K]로 저장합니다. flag를 통해 방문 여부를 확인하며 DFS로 탐색합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/16432_%EB%96%A.. 2022. 1. 13. [백준] 9205번 - 맥주 마시면서 걸어가기 (C++) 문제 및 풀이 문제) 백준 - DFS - 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 좌표를 모두 입력받아 20*50을 넘는 점을 제외하고 graph에 인접 리스트 형태로 나타냅니다. DFS를 통해 탐색하면서 visited [N+1] 번째를 방문 여부에 따라 'happy' 또는 'sad'를 출력합니다. C++ 소스코드) Full code) https://github.com/Chocochip101/BOJ_Solution/blob.. 2021. 12. 26. [프로그래머스] 코딩테스트 고득점 Kit - 네트워크 (C++) 문제 및 풀이 문제) 프로그래머스 - DFS - 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 0번째부터 n번째까지 DFS로 네트워크를 탐색합니다. solution 함수에서 만약 visited하지 않았던 컴퓨터면 새로운 네트워크이므로 answer에 1을 더해줍니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/Programmers/blob/main/%EC%B.. 2021. 12. 7. [백준] 1325번 - 효율적인 해킹 (C++) 문제 및 풀이 문제) 백준 - DFS - 효율적인 해킹 https://www.acmicpc.net/problem/1325 2021. 11. 29. [백준] 13565번 - 침투 (C++) 문제 및 풀이 문제) 백준 - DFS - 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net dfs를 통해서 visited 배열을 갱신 후, inner side에 도달했는지 확인한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/13565_%EC%B9%A8%ED%88%AC.cpp GitHub .. 2021. 11. 1. 이전 1 2 다음 반응형
