KPU CE

그래프의 탐색이란 루트부터 아래 노드들 까지 모든 정점을 방문하는 것이다. 깊이 우선 탐색(DFS)이란? 깊이 우선 탐색은 트리나 그래프에서 한 루트로 최대한 깊숙이 들어가서 탐색한 후 다시 돌아와 다음 루트도 깊이 탐색하는 방법이다. 일반적으로 재귀 호출을 사용하여 구현한다. 단순 검색 속도는 BFS보다 느리다. 장점 1. 목표 노드가 깊이 있으면 빨리 구할 수 있다. 2. 매번 기억하는 노드가 하나이므로 저장 공간의 수요가 적다. 단점 1. 목표노드가 없는 경로의 깊이 빠질 수 있다.-> 시간이 많이 걸릴 수도 있다. 알고리즘 설명 그림과 같이 루트가 1인 트리가 있다. 루트가 1이므로 루트 1에 대하여 DFS를 하면 최대 노드 3까지 내려가게 된다. 다음 루트는 이제 노드 2가 되어서 노드 2에 대..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해결 1. 다이나믹 문제이지만 재귀를 이용하여 풀었다. 2. 각 DAY마다 재귀를 이용하여 상담이 가능한 날짜를 탐색했다. 코드 1234567891011121314151617181920212223#include using namespace std;int N,Max = 0;int ary[16][2];void DFS(int node,int count){ if(count >= Max){Max = count;} for(int i = node;iN){continue;} DFS(ary[i][0]+i,count+ary[i][1]); } ..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 풀이 1. 입력값이 주어지면 무방향 인접 리스트를 이용하여 데이터를 저장한다. 2. 인접 리스트를 모른다면 나의 블로그의 인접 리스트 포스팅을 보고 와야 한다. 3. 인접 리스트로 저장 후 DFS알고리즘을 통해 노드 1~N까지 DFS알고리즘을 돌려준다. 4. 여기서 포인트는 visit 배열과 visited 배열 두..

문제 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. 인접 리스트로 정점들을 저장한다. 2. 1~N까지 방문하지 않은 노드들을 DFS 한다. 3. 방문할 때 마다 cnt를 해준다. 코드 1234567891011121314151617181920212223242526272829303132333435#include #include #define Max 1001using n..

문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 1. DFS를 이용하여 1~N까지의 숫자를 탐색한다. 2. ex) 1에 대하여 탐색한다면 1에 대하여 깊이 탐색한 후 지나는 모든 노드들을 visit 한다. 3. visit이 true이면 map [1][j] = 1로 인접 행렬을 만든다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

최소 공통조상이란? 두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을 알아보도록 하겠다. 위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다. 여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다. 하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다. 바로 본론으로 들어가자면 최소 공통 조상 알고리즘은 1. 두 노드의 깊이를 확인한다. 2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다. 3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다. 4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다. 5. 같아지는 지점이..

문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 1. BFS를 이용해서 탐색을 할 때 방문할 노드가 개방 가능 조건에 있다면 border배열을 true로 해준다 2. true로 되어 있는 노드를 하나 방문 후 연결되어 있는 모든 true노드를 방문한다. 3. 방문할 때마다 cnt++ 을 해줘서 몇 개의 노드를 방문해 줬는지와 sum+=map [y][x]를 해줌으로써 방문한 노드들의 평균값을 구할 수 있다. 4. 방문을 마친 노드..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 문제해결 1. DFS를 이용해서 가장 경로가 큰 노드를 찾는다. 2. 가장 큰 노드를 루트로 하고 다시 DFS를 해준다. 코드 ide.goorm.io/shared_files/sksj0111_9c7f680ec5975ba4aae255f776fdbd4c1605924147580 1167.cpp - goorm 구름IDE에서 공유된 소스코드를 볼 수 있는 페이지입니다. ide.goorm.io..