https://www.acmicpc.net/problem/4803 예제6 31 22 33 46 51 22 33 44 55 66 61 22 31 34 55 66 40 0---ans : Case 1: A forest of 3 trees.Case 2: There is one tree.Case 3: No trees.주어진 그래프에서 트리가 몇 개 존재하는지 판단하는 문제이다.트리의 조건은 사이클이 없는 연결 요소이고 n-1개의 간선으로 이루어져 있고 임의의 두 정점에 대해 경로가 유일하다는 것인데, 이 조건을 이용해서 찾아야 한다.처음에는 연결 요소를 찾고 사이클이 없는지 판단한 뒤 n-1개의 간선으로 이루어져 있고 모든 정점 간 경로가 유일한지 체크하려 했다. 그런데 bfs를 사용해서 연결 요소를 찾다 보니 ..

[바킹독님 블로그 정리 글입니다!] [실전 알고리즘] 0x19강 - 트리이번 시간에는 트리를 다루어봅시다. 바로 본론으로 들어가겠습니다. 특별히 트리에서의 BFS와 DFS를 또 익힐 예정입니다. 저희는 0x16강에서 이진 검색 트리를 배우며 이미 트리라는 개념을 적당blog.encrypted.gg 트리의 기본적인 특성부터 알고 가자면, 트리의 정의는 무방향이면서 사이클이 없는 연결 그래프이다. V개의 정점에 대해 V-1개의 간선을 가지는 사이클이 없는 연결 그래프라고 생각하면 된다. 트리에서의 BFS는 그래프의 BFS와는 조금 다른 의미를 가진다. 그래프의 BFS는 특정 정점에서 연결된 점을 찾는 용도로도 많이 사용되었는데, 트리는 연결 그래프이므로 방문 순서와 부모 배열, depth 배열을 채울 수 있..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 조건제한이 걸린 경로를 찾는 문제이다. 가장 먼저 떠올린 풀이는 dp [i][j]를 (i, j)까지 도달할 수 있는 경우의 수로 두고 네 방향 모두에서 (i, j)로 도달할 수 있으므로 4방향을 순차적으로 채우는 방법이었다. 이 방법은 아래와 같은 케이스를 잡아내지 못했다. 다음에 떠올린 방법은 DFS였다. DFS에서 백트래킹 느낌으로 메모이제이션을 떠올릴 수 있었다. 어떤 점 (i, j)에서 더 이상 갈 수 있는 곳이 없으면 (i, j)에 도달하면 바로 종료하는 방..

2023.10.25 - [알고리즘/문제풀이] - [BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 예제가 굉장히 많아 백준에서 참고하시길 바랍니다. 주의할 점은 백준의 test case에는 4번 cctv에 대한 검증이 부족하므로 개인적으로 테스트해볼 것을 추천합니다. 먼저 문제는 최대 8 * 8 크기에 최대 8개의 cctv 각 cctv는 최대 4방향이므로 4^8 = 65536이다. 따라서 완전탐색으로도 충분히 시간안에 풀 수 있을..

BFS는 큐를 이용한 탐색의 한 방법으로, 너비 우선 탐색이다. 너비 우선 탐색이라고 하면 감이 잘 안 올 텐데, 알고리즘부터 보자. 큐에 시작점을 push 한다. 큐의 front를 저장해 두고 pop 한다. pop한 원소에 방문표시를 해둔다. 저장해 둔 원소의 상하좌우 중 방문가능한 원소를 큐에 집어넣는다. 큐가 빌 때까지 2~3을 반복한다. 이를 바탕으로 Flood Fill을 해보자. Flood Fill은 흔히 그림판에 있는 페인트 기능으로, 경계선을 기준으로 색을 일괄 변경하는 기능이다. 어떻게 구현하냐면, 어떤 칸의 상하좌우를 살펴보고 같은 색이라면 포함시키고, 아니라면 경계선으로 설정하는 느낌으로 구현하면 되는데 BFS를 사용하면 쉽게 구현할 수 있다. BFS의 구현은 거의 정석적으로 정해져 있..

예제 입력 1 5 5 1 1 4 1 2 2 3 2 4 3 4 예제 출력 1 1 4 3 2 0 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 무방향 그래프를 구현하고 오름차순으로 DFS를 구현한 뒤 정점들에 대한 방문 순서를 차례로 출력하면 되는 문제이다. DFS의 기본 이론은 시작 정점에 대해 방문할 수 있는 정점 중 정해진 기준(문제에서는 오름차순)에 따라 방문하고, 다시 방문한 정점에 대해 방문할 수 있는 정점 중 기준에 따라 반복하..