알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 + BFS를 이용한 문제입니다. 어떠한 최단 경로가 있을 때, 해당 경로를 지우고 난 뒤의 다음 최단 경로를 찾는 문제입니다. 최단 경로를 찾는 것은 간단합니다. 다익스트라 알고리즘을 사용하면 찾을 수 있습니다. 그 다음인 최단 경로를 지우는 것이 문제인데, 이는 BFS를 사용하면 됩니다. BFS를 통해 최단 경로를 지우기 전에, 다익스트..

문제 링크입니다. https://www.acmicpc.net/problem/24484 24484번: 알고리즘 수업 - 깊이 우선 탐색 6 정점 1번에서 정점 4번을 방문한다. 정점 4번에서 정점 3번을 방문한다. 정점 3번에서 정점 2번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 4, 3, 2, 0이다 www.acmicpc.net 해당 문제에서 내림차순을 해주면 되는 문제입니다. 자세한 설명은 해당 글을 참고해주세요. https://junseok.tistory.com/298 백준 24483 - 알고리즘 수업 - 깊이 우선 탐색 5(C++) 문제 링크입니다. https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업..

문제 링크입니다. https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업 - 깊이 우선 탐색 5 정점 1번에서 정점 2번을 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 3번에서 정점 4번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 3, 4, 0이다 www.acmicpc.net DFS를 이용한 문제입니다. 노드의 방문 순서 및 노드 깊이를 구하는 문제였습니다. 방문 순서는 변수 하나를 통해 저장해주면 됩니다. 저는 Count 변수를 하나 만들어, 노드를 방문할 때마다 1씩 증가해 넣어줬습니다. 노드 깊이는 방문 순서와 다르게 다른 노드를 방문했다고 1씩 증가하는게 아닙니다. 이전 노드의 깊이에서 1..

문제 링크입니다. https://www.acmicpc.net/problem/24482 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net DFS를 이용해 방문 노드의 깊이를 구하는 문제입니다. 방문 노드의 순서가 아닌, 깊이를 방문하는 것이기에, 노드를 방문할 때마다, 1를 증가해 값을 입력하면 안됩니다. 또한, 인접 노드는 내림차순으로 방문하기에, 정렬 기준을 세우거나, reverse를 사용해 탐색을 해야했습니다. 자세한 것은 코드를 참고해주세요. #define..

문제 링크입니다. https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net DFS를 이용해 노드 깊이를 구하는 문제였습니다. 방문 순서가 아닌, 방문 깊이이기 때문에, 정점을 방문할 때마다 1씩 증가해서 넣으면 안됩니다. void dfs(int x, int cnt){ check[x] = cnt; for(int i = 0 ; i < connect[x].size(); i++){ int xx = connec..

문제 링크입니다. https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 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를 이용해 그래프 탐색을 할 때, 노드 방문 순서를 출력하는 문제입니다. 노드를 방문할 때, 인접 정점은 내림차순으로 방문한다는 것이 중요했습니다. DFS 코드는 재귀 함수를 이용했습니다. DFS를 탐색하기 전에, 노드를 정렬..

문제 링크입니다. https://www.acmicpc.net/problem/24479 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를 이용한 문제입니다. 시작점이 주어졌을 때, 다른 정점을 몇번만에 방문하는지를 출력해야됩니다. 저는 check, Cnt 배열을 이용해, check 배열에는 방문 여부를, Cnt 배열에는 방문 순서를 저장했습니다. 탐색을 진행하기 전에, 오름차순 방문을 위해 오름차..

문제 링크입니다. https://www.acmicpc.net/problem/24446 24446번: 알고리즘 수업 - 너비 우선 탐색 3 너비 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2, 4번 노드이다. 3번 노드는 2번 또는 4번 노드의 자식이다. 5번 노드는 1번 노드에서 방문 될 수 없다. www.acmicpc.net 간단한 BFS 문제였습니다. 양방향 그래프와 시작점이 주어질 때, 1~N번까지 깊이를 구하는 문제입니다. 저는 check 배열을 하나 만들었습니다. check 배열의 값을 전부 -1로 초기화한 뒤, X번이 탐색될 때마다 연결된 정점의 check 값에서 1 더한 값을 저장해줍니다. 탐색이 모두 끝난 뒤, check 배열의 값을..

문제 링크입니다. https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 생각이 필요한 다익스트라 문제였습니다. 목적지 후보지와 출발점, 듀오가 이동한 정점 2개가 주어졌을 때, 어떤 후보지에 향하고 있었는지를 구하는 문제입니다. 이 문제를 풀기 위해서는 S-G or G-S 간선을 이동했는지를 구하는 것이 핵심입니다. 출발점에서 목적지 후보지까지 각각 이동한 간선들을 모두 저장하는 것도 방법이지만, S, G정점 활용해 최소 비용을 비교하는 것이 ..

문제 링크입니다. https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 구현력을 요구하는 BFS 문제였습니다. 두 사람이 좌우에서 막대기를 던지면서 미네랄를 부술때, 마지막의 미네랄 모양을 구하는 모습입니다. 문제에서 주어진 조건을 보면 1. 좌 -> 우 -> 좌 와 같이 돌아가면서 던진다. 2. 아래층이 1이며 윗층이 N이다. 3. 떨어지는 클러스터는 1개이다. 해당 조건을 기본적으로 알고 문제를 접근해보겠습니다. 문제를 크게 나누면 3개로 나눌 수 있습니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 검을 얻었을 경우, 검을 얻지 못했을 경우로 나눠서 탐색을 진행해주는 것이 중요한 문제였습니다. 검을 얻었을 때는 벽을 제한없이 부실 수 있으며, 검을 얻지 못했을 경우는 정해진 길로밖에 가지 못합니다. 따라서 용사가 탐색을 하는 방법은 1. 검을 얻었을 경우 2. 검을 얻지 못했을 경우 이 2가지로 나눌 수 있습니다. 2가지 방법을 BFS에서 같이 돌려줘야 하는..

문제 링크입니다. https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net BFS를 사용해 푸는 문제였습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; int N, M; char map[251][251]; int check[251][251]; int dx[4] ..