[Gold III] 웜홀 - 1865 [문제 링크](https://www.acmicpc.net/problem/1865)🗝️알고리즘 분류최단 경로벨만-포드💻문제 정의N개의 지점이 존재하는 마을에서, 한 지점에서 출발하여 웜홀을 통해 시작 지점으로 돌아왔을 때, 출발 시간보다 이전 시간대로 돌아온 경우 "YES"를 출력하고 아니면 "NO"를 출력하는 문제이다. 즉, 주어진 마을을 그래프로 표현하였을 때, 어느 한 정점에서 부터 사이클이 발생하고, 그 사이클이 무한한 음수 사이클을 가지는지를 찾는 문제이다. 💡접근 및 설계사이클 발생 및 음수 여부를 판단하기 위한 알고리즘으로 벨만-포드 알고리즘을 활용한다. ✏️알고리즘 풀이def bellman_ford(start): # 시작 노드 거리 초기화 ..

[Gold IV] 플로이드 - 11404 [문제 링크](https://www.acmicpc.net/problem/11404)🗝️알고리즘 분류최단 경로플로이드-워셜💻문제 정의각 도시마다 다른 도시로 이동할 때의 최단 경로를 차례로 출력하는 프로그램을 작성하는 문제이다. 💡접근 및 설계정점 N개에 대하여, 모든 정점으로 이동하기 위한 최단 경로 비용을 구해야 한다. 플로이드-워셜 알고리즘을 활용하여 각 정점에서 다른 정점 사이의 최단 경로를 구할 것이다. 다익스트라 알고리즘보다 플로이드-워셜 알고리즘이 더욱 간결하고 구현이 쉬워 이를 이용한다. 플로이드-워셜 점화식은 다음과 같다. ✏️알고리즘 풀이for k in range(1, N+1): for a in range(1, N+1): f..

[Gold IV] 스도쿠 - 2580 [문제 링크](https://www.acmicpc.net/problem/2580) 🗝️알고리즘 분류백트래킹💻문제 정의풀다 만 스도쿠가 주어졌을 때, 이를 완성하는 프로그램을 작성하라. 💡접근 및 설계빈칸에 숫자를 하나 씩 넣어보면서, 스도쿠 완성 조건을 하나 씩 따져보면서 백트래킹 한다. ✏️알고리즘 풀이for i in range(1, 10): # 1 ~ 9의 값을 넣어봄 if (c[x][i] == 0) and (c2[y][i] == 0) and (c3[square(x, y)][i] == 0): c[x][i] = c2[y][i] = c3[square(x, y)][i] = True a[x][y] = i # 값을 넣고 if..

[Gold IV] N-Queen - 9663 [문제 링크](https://www.acmicpc.net/problem/9663)🗝️알고리즘 분류백트래킹💻문제 정의NxN 크기의 체스판에 N개의 퀸이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 문제이다. 💡접근 및 설계퀸은 상하좌우대각선 8방향으로 움직일 수 있다. 즉, 같은 열, 같은 행, 같은 대각선 내 두 개 이상의 퀸이 존재하지 않도록 퀸을 배치해야 한다. NxN의 공간에서 N개의 퀸을 놓기 위해 백트래킹을 활용한다. 먼저 퀸을 한 개 놓고 난 다음, 두 번째 퀸을 어디에 놓을 수 있을지를 판단한다. N개의 퀸을 놓았다면 카운트를 증가하고 N-1로 돌아가 다음 경우의 수를 생각한다. 해당 과정이 백트래킹이다. ✏️알고리즘 풀이count = 0ro..

[Gold IV] 트리의 지름 - 1967 [문제 링크](https://www.acmicpc.net/problem/1967)🗝️알고리즘 분류트리의 탐색깊이 우선 탐색(DFS)💻문제 정의주어진 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 구하는 문제이다. 💡접근 및 설계문제에서 트리의 루트 노드는 항상 1번 노드라고 명시되어 있다. 따라서 루트 노드로 부터 가장 멀리 떨어진 노드를 찾고, 해당 노드에서 부터 가장 멀리 떨어진 노드를 찾은 다음, 두 노드 사이의 거리를 구하는 방식으로 접근하였다. ✏️알고리즘 풀이graph = [[] for _ in range(N+1)] # 트리 초기화for _ in range(N-1): a, b, c = map(int, input().split()) ..

[Gold V] 트리와 쿼리 - 15681 [문제 링크](https://www.acmicpc.net/problem/15681)🗝️알고리즘 분류트리의 탐색깊이 우선 탐색(DFS)💻문제 정의트리가 주어졌을 때, 쿼리에 대한 답변을 출력하는 문제이다. 트리는 가중치와 방향성이 없고, 루트는 있다. 쿼리는 정점 U를 루트로 하는 서브트리의 정점의 개수를 구하는 것이다. 💡접근 및 설계루트가 있는 트리를 설계한 후, 쿼리로 부터 오는 정점 U가 루트가 되는 서브트리의 정점을 개수를 구해야 한다. 일반적인 dfs로 접근하였고, 각 정점마다 정점이 루트일 때, 서브트리의 개수를 포함시키도록 하였다. ✏️알고리즘 풀이visited = [False for _ in range(N+1)] # 방문 체크 표시 및 서브트..