![]()
1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다. 1. 조건을 같지 않을때로 걸고 BFS를 돈다 2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다. 3. 다시 BFS를 돈다. 2. Code #include using namespace std; int n; vector vec(101, ""); vector vis(101,..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. Logic - 기본 다익스트라 문제이다. 문제에서 나온대로 한 정점에서 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘을 사용하면 풀 수 있다. 다 돌고 배열에서 값만 하나씩 출력해주면 되는 문제 2. Code #include using namespace std; const int INF = 10000000; // 시작 노드에서 해당 노드까지의 경..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Logic - 다익스트라는 한 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 이 문제는 한 정점에서 모든 정점으로 가는 최단거리 + 다시 집에가는 최단거리 두개를 구해서 더해야 한다 2. Code #include using namespace std; const int INF = 987654321; //최소 비용 배열 int d[1001]; vect..
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1. Logic - 문제를 읽고 회전이나 대칭을 해도 된다고 쓰여있었기 때문에 재귀를 통해서 정사각형 한 칸씩 차지해 나가며 해당 칸에 있는 숫자를 더해서 Max값을 더하면 될것 같다고 생각했다. - 재귀를 통해서 가기때문에 DFS로직을 생각했고 다른 모양은 다 가능 하지만 ㅗ, ㅏ, ㅜ, ㅓ 모양은 재귀를 통해서 구할 수 없기 때문에 따로 구해줘야 한다. 2. Code #include using..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - BFS함수 안에서 처음 들어갔던 문자와 vec[nexty][nextx]가 같을때만 queue에 push하면 해당되는 구역만 구할 수 있을 것이라고 판단함. - BFS함수의 Logic 대로 정상 BFS를 돈 후 for문을 통해 Red값과 Green값을 똑같은 값으로 만들어주기 위해 for문을 돌아서 R > G 또는 G > R로 변환시킨 후 다시 BFS돈다 2. Code #..
