개발자 퉁이리

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 단순 트리의 부모만 구하면 되는 문제다. DFS, BFS 두 가지 풀이 방법이 있는데 DFS로 풀어봤다. vector에 값을 대칭으로 입력한다. 그리고 자식노드에 하나씩 방문하여 부모를 지정해주는 로직으로 풀었다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS 문제이다. 시작 값을 bfs() 함수에 넣고 방문할 때마다 값을 하나씩 올려준다. 그리고 마지막에 목표값에 대해 출력하면 된다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 102..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 다른 bfs와 비슷하지만 이번에는 대각선까지 고려해주어야 한다. 상, 하, 좌, 우, 우상, 우하, 좌하, 좌상. 총 8개의 방향을 탐색해 방문 체크해주었다. 그리고 reset() 함수를 직접 만들어주어 결괏값을 출력하면 계속 리셋해주고 반복해주었다. ⊙ ..

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 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS로 접근하여 문제를 풀었다. 1. 값을 입력받으면 대칭적으로 '1' 값 저장 2. 1부터 시작, queue에 '1' 값 넣고 방문 표시, 반복 3. N까지 반복하는데 방문을 안 했다면 count..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS 알고리즘 돌리고 T만큼 반복해야하니 reset()이라는 초기화 함수를 만들어줬다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 51 int M,N,K; int arr[MAX][MAX]={0,}; int vi..

https://www.acmicpc.net/problem/1260 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 DFS와 BFS 알고리즘을 사용하여 푸는 문제이다. DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다. DFS의 구현은 스택 또는 재귀 함수로 구현한다. BFS의 구현은 큐를 이용해서 구현한다. ⊙ 문제 풀이 #include #include using namespace std; int n,m,v; int arr[1001][1001]; bool visit[1001]; void reset_visit() { for (auto i=1;i y; arr[x][y]=1; arr[y][x]=1; } reset_v..