백준문제풀이/DFS
11725번-트리의 부모 찾기
문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근방법 1) 접근 사고 깊이 우선 탐색에서 가장 깊은 탐색을 진행한 뒤 재귀가 끝난 경우를 노드의 현재 번호값에 저장하면 되는 문제였습니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n; const int MAX = 100005; vector edge[MAX]; bool visited[MAX]; int ret[MAX]; void DFS(int cur) { visited[c..
2606번-양
문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 접근방법 1) 접근 사고 1. DFS 탐색을 통해 1번 바이러스와 연결된 간선들을 탐색해주면 됩니다. 2. 바이러스의 숙주인 1번은 제외하고 출력해야 합니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n, m, ans; const int MAX = 105; vector board[MAX]; bool visited[M..
11724번-연결 요소의 개수
문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 접근방법 1) 접근 사고 1.연결 요소의 개수를 구해주면 되기 때문에 방문한 노드 지점을 visited 배열을 사용해 체크해줍니다. 2. 방문한 지역은 visited를 사용해 제외해주었기 때문에 DFS 시도횟수의 의미가 전체 연결 개수의 의미를 의미하므로 DFS 시도 횟수를 출력해줍니다. 2) 시간 복잡도 O(V + E) 3) 실..
14888번-연산자 끼워넣기
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근방법 1) 접근 사고 가능한 모든 연산의 경우를 탐색해줘야 하는 문제였습니다. DFS 알고리즘을 통해 모든 경우의 수를 구해주었습니다. 2) 시간 복잡도 O(V + E) 3) 배운 점 매개변수를 적절하게 사용하면 코드의 라인이 절약될 수 있다는걸 느낀 문제입니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..