전체 글84 백준 21940번: 가운데에서 만나기 (C++) 문제링크 https://www.acmicpc.net/problem/21940 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단 거리를 계산 해 놓는다. 우선순위 큐를 활용하여 를 넣어서 왕복 시간이 가장 적은 도시를 바로 꺼낼 수 있게 만든다. 왕복 시간이 가장 작은 것이 가장 위쪽에 존재하므로 우선 해당하는 도시의 번호를 출력한다. 왕복 시간이 가장 작은 것이 여러 개라면 해당 도시 번호까지 전부 출력한다. 위 설명의 시퀀스를 이해하고 아래 코드를 참고하자. 코드 #include using namespace std; int n, m, a, b, c, k, num, ans_min; vector friends.. 2024. 2. 3. 백준 1238번: 파티 (C++) 문제링크 https://www.acmicpc.net/problem/1238 풀이방법 해당 문제는 플로이드 알고리즘 및 다익스트라 알고리즘 모두 사용하여 해결 할 수 있다. 플로이드 알고리즘 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단거리를 계산 해 놓는다. 단 방향이므로 특정 노드에서 특정 노드로 갈 때와 올 때 거리가 다를 수 있으므로 그 두 개를 더한 값을 MAX값과 비교하고, 더 큰 값을 다시 MAX에 저장한다. 위 설명의 시퀀스와 그래프 그림을 통해서 문제를 이해하고 아래 코드를 참고하자. 다익스트라 알고리즘 solve 함수를 만들어서 st,en인자를 받아서 st부터 en까지 최단 경로를 바로 구할 수 있게 만든다... 2024. 2. 3. 백준 11780번: 플로이드2 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하고 단순히 최단 거리 뿐만 아니라 특정 노드에서 노드로 이동하는 최단 경로가 어떻게 진행되는지도 출력해야 하는 문제다. 따라서 경로 복원에 필요한 nxt배열을 추가로 삽입하여 문제를 해결할 수 있다. 해당 문제에 대한 상세 풀이는 아래 바킹독님 영상을 참고하자. 또한 플로이드 알고리즘이나 경로 복원에 대한 개념이 부족하면 아래 영상을 통해 알고리즘에 대한 개념을 익히자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int I.. 2024. 2. 3. 백준 11404번: 플로이드 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하는 문제이다. 해당 문제에 대한 상세 풀이나 플로이드 알고리즘에 대한 이해가 필요하면 아래 영상을 참고하자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int INF = 0x3f3f3f3f; int d[105][105]; int n, m; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i > a >> b >> c; d[a].. 2024. 2. 3. 백준 1647번: 도시 분할 계획 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 우선 마을 하나하나를 그래프의 노드라고 생각한다. 그 상태로 최소 신장 트리를 만든다. 그럼 모든 마을이 연결되어있고 가중치의 합이 최소인.. 2024. 2. 3. 백준 16398번: 행성 연결 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 코드 #include using namespace std; #define X first #define Y second int n; vect.. 2024. 2. 3. 백준 9372번: 상근이의 여행 (C++) 문제링크 https://www.acmicpc.net/problem/1368 풀이방법 해당 문제는 신장 트리 알고리즘의 원리를 이용해서 바로 답을 구할 수 있다 신장 트리의 원리는 다음과 같다. 신장 트리란? 신장 트리(Spanning Tree)는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 따라서 위 이론을 문제에 적용하면 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수는 즉, N개의 노드(비행기가) 있을 때 가능한 최소의 간선 수.. 2024. 2. 3. 백준 1368번: 물대기 (C++) 문제링크 https://www.acmicpc.net/problem/1368 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 다만, 이 문제를 해결하는데 가장 중요한 점은 그래프를 목적에 맞게 변형하는 것이다. 그 이유는 직접 논에 우물을 파는 경우를 그래프로 표현할 수가 없기 때문이다. 바로 방법을 알려주면 직접 논에 우물을 파는 경우를 추가적인 노드를 만들어서 추가된 노드에 가중치를 주는 방식으로 구현할 수 있다. 아래 그림을 보면 이해가 될 것이다. 5번 노드를 추가해서 해당 노드로 직접 논에 우물.. 2024. 2. 3. 이전 1 2 3 4 5 6 7 ··· 11 다음
