DFS ( 깊이 우선 탐색 ) 깊이 우선 탐색은 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기에 대한 탐색을 완전히 끝내고 다음 분기로 넘어가는 방식의 탐색을 의미한다. 가능한 한 방향으로 깊게 내려가며 노드를 탐색한다. DFS의 동작 방식시작 노드 선택탐색을 시작할 노드를 선택방문 및 기록현재 노드를 방문하고, 방문을 기록( 중복 방문 방지)자식 노드 탐색현재 노드에 연결된 인접 노드 중 아직 방문하지 않은 노드가 있다면 그 노드로 이동하여 탐색 진행백트랙킹더 이상 탐색을 진행할 수 없는 경우(현재 노드의 인접 노드를 모두 방문) 이전 단계의 노드로 되돌아감이 과정을 반복하며 탐색을 진행탐색 종료모든 노드를 탐색했거나, 특정 조건을 만족하는 노드를 찾은 경우 탐색을 종..

문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N  출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력8예제 출력92해결방법N-Queen 문제는 Backtracking 전략을 통해 해결할 수 있는 가장 대표적인 문제중 하나이다. Queen을 NxN 체스판에 N개 두기 위해서는 각 행에 오직 하나의 퀸만이 올 수 있다. 따라서 배열을 하나 만들어서 각 행에 퀸의 위치를 기록할 수 있도록 한다. 각 행들에 대해 퀸 위치를 모두 탐색하되, 조건에 맞지 않는 경우가 발생한다면 그 이후는 고려하지 않고 가지치기를 ..

백트랙킹(Backtracking) 이란?백트래킹은 한정 조건에 대해 해를 찾는 탐색 및 최적화 문제의 해결 전략이다. 백트래킹은 모든 경우에 대해 탐색을 수행하는 과정에서 불필요한 경로는 배제하여 효율성을 높이는 방식으로 동작한다. 한정조건에 대해서 경우의 수를 시도하기 때문에 단순 다중 for문을 사용하는 것보다 효율적으로 동작한다.  Backtracking의 문제 해결 전략문제를 풀기 위한 모든 가능한 해의 조합을 정의함각 단계에서 현재 상태가 문제의 한정 조건을 만족하는 지 검사하고, 해가 될 수 없는 경로라면 가지치기를 통해 정답 경로에서 배제함정답이 될 수 있는 경로를 따라 재귀적으로 진행을 한다. 특정 경로가 조건을 만족하지 못하면 이전 단계로 돌아가 경로를 탐색함 탐색하다가 문제를 해결하면 ..

문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째..

문제n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수..

문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데,..

[백준] 11779 - 최소 비용 구하기 2문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.입력 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버..

다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘 탐색 과정[step 1] 출발 노드와 도착 노드를 설정[step 2] 출발 노드를 기준으로 각 노드의 최소 비용을 저장 ( 갈 수 없다면 INF로 설정)[step 3] 방문하지 않은 노드 중에서 비용이 가장 적은 노드를 선택[step 4] 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려하여 최소 비용 갱신[step 5] 3,4 과정을 반복 다익스트라 알고리즘 탐색 예시이차원 배열 형태로 그래프를 처리출발/도착12345610251INFINF2INF032INFINF3INF30INFINF54INFINF301INF5INFINF1INF026INFIN..