while (1): study();

문제 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 max_dist: max_dist = ..

플로이드-워셜 알고리즘이 전체 노드에 대한 최소거리를 구하는 데 사용된다면, 다익스트라 알고리즘은 특정 노드에 대한 최소거리를 구하는 것에 특화되어 있습니다. 구체적으로는 다음과 같은 과정을 거칩니다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 5. 위 과정에서 3~4 반복 수행 아래는 기본적인 방법론을 따라 구현한 소스코드입니다. # n :노드 개수, m : 간선 개수 # start = 시작 노드 INF = int(1e9) graph = [[] for i in range(n + 1)] visited = [False] * (n + 1) distan..

문제 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 입력 조건 - 첫째 줄에 테스트 케이스의 수 T(1

문제 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다. - 1번 학생의 성적 < 5번 학생의 성적 - 3번 학생의 성적 < 4번 학생의 성적 - 4번 학생의 성적 < 2번 학생의 성적 - 4번 학생의 성적 < 6번 학생의 성적 - 5번 학생의 성적 < 2번 학생의 성적 - 5번 학생의 성적 < 4번 학생의 성적 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에 학생들의 수 N(2

그래프의 최단경로를 구할 수 있는 알고리즘이다. 특히 '모든 노드에 대해서 최단거리를 구하고 싶을 때 사용'한다. (반면, 다익스트라 알고리즘은 특정 노드 하나의 최단거리를 구하는 것에 특화되어 있다). 기본적으로 주어진 그래프에 대해서 다음과 같은 점화식을 수행한다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 즉 주어진 그래프에 대해서 특정 원소를 지나서 도달할 수 있는 경우의 수들을 차례로 고려하며 업데이트하는 것이다. 이때 i, j, k에 대해서 모두 노드의 개수만큼 순회해야하기 때문에 플로이드-워셜 알고리즘의 시간복잡도는 (O(N^3))이다. 따라서 노드의 개수가 1000개만 되어도 사용할 수 없다. 정리해보자면 다음과 같다. 장점: 구현이 매우 간단하다. ..

출처: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 이용한 최단경로 문제는 나오기만 하면 정말 땡큐인 문제인 듯합니다. 이 문제 역시 그래프의 노드 개수가 100개 이하이므로, 플로이드-워셜 알고리즘을 사용하여 손쉽게 해결할 수 있습니다. 플로이드-워셜 알고리즘에 대한 조금 더 상세한 설명은 다음 링크를 참조바랍니다. 링크: https://jcy1996.tistory.com/24?category=958980 플로이드..