판교의 메타몽

링크 : 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) 모든 노드를 순회한다. (..

링크 : www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net 문제 풀이는 다음과 같았다. (1) 방문하지 않은 섬을 DFS한다. (2) 해당 섬을 방문한 것으로 표기한 뒤, 해당 섬의 전방위에 섬이 있을 경우 그 위치를 DFS한다. (3) 만약 해당 섬의 위치가 주어진 영역을 초과하거나, 섬이 아니었거나, 이미 방문했던 전적이 있으면 DFS를 종료한다. #include #include #include #include //memset using namesp..

백 트래킹 (Back Tracking) 말 그대로 왔던 길을 다시 추적하는 알고리즘. 즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면 모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. Brute Force와는 차별화된 Back Tracking의 특징은 필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다. 이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다. 백 트레킹에는 크게 3가지 종류가 있다. 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search), 큐를 이용하는 BFS(너비우선탐색, Breadth First Search) BFS/HS(최선우선탐색,..