출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 40, p 390 프로그래머스의 가장 먼 노드 문제와 매우 유사한 문제였습니다. 마찬가지로 다익스트라 알고리즘으로 풀이했습니다. 다익스트라 알고리즘 코드대로 graph, distance를 초기화하고 입력에 맞게 graph 정보를 저장했습니다. 헛간을 잇는 통로가 양방향이고, weight가 따로 없기 때문에 이 부분만 기존 코드를 수정했습니다. 이후 다익스트라 알고리즘을 실행하여 distance를 구한 뒤, 가장 먼 헛간의 최단거리만큼 떨어진 헛간들 중 헛간 번호가 가장 작은 것, 가장 먼 헛간의 최단거리, 가장 먼 헛간의 최단거리만큼 떨어진 헛간들의 개수를 순서대로 반환했습니다. import sys import heapq INF = int(1..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 39, p 388 다익스트라 알고리즘을 활용해 풀이했습니다. 우선 입력을 받아 하나의 테스트 케이스는 N*N 리스트로 정리하고, 각 테스트 케이스를 spaces라는 리스트에 저장했습니다. 화성 탐사 기계는 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다고 했으므로, 그래프의 인접한 노드 대신 상하좌우의 좌표를 탐색하며 풀이했습니다. 이때 N*N 리스트 밖으로 나가 IndexError가 발생하는 것을 방지하기 위해 인덱스가 0~N-1 사이인지 확인해주었습니다. 마지막으로 가장 위 칸인 (0,0)을 지나는데도 에너지가 소모되므로, 다익스트라 알고리즘이 끝난 후에 (0,0)을 지나는데 소모되는 에너지를 더해주었습니다. import fileinput ..

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 38, p 386 플로이드 워샬 알고리즘을 활용해 풀이했습니다. 현재 학생을 제외한 나머지 학생들이 현재 학생보다 성적이 낮은지, 높은지 모두 알면 그 학생의 정확한 순위를 알 수 있습니다. A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 하면, 플로이드 워샬 알고리즘 수행 후 그래프의 n번째 가로줄(행)에 INF가 아닌 숫자가 있으면 그 인덱스의 학생은 n번째 학생보다 성적이 높다는 의미입니다. n번째 세로줄(열)에 INF가 아닌 숫자가 있으면, 그 인덱스의 학생은 n번째 학생보다 성적이 낮다는 의미입니다. 따라서 n번째 행과 열에서 INF가 아닌 값을 가지는 인덱스 + 자기 자신의 인덱스(n)을 합쳤을 때, 1 ~..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 3가지 수정사항을 제외하고 다익스트라 알고리즘을 그대로 활용해 풀이했습니다. (1) 간선이 양방향이므로 graph에 정보를 저장할 때 두 가지 방향을 모두 저장했습니다 (2) 간선에 weight가 없으므로 일괄적으로 1로 통일했습니다 (3) 마지막에 답을 반환할 때 1번 노드를 제외한, 2번에서 마지막 노드까지의 거리 중 최댓값을 구하고, 이 최댓값과 같은 거리를 갖는 노드의 개수를 반환하도록 했습니다 import heapq def..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 2가지 수정사항을 제외하고 다익스트라 알고리즘을 그대로 활용해 풀이했습니다. (1) 하나의 도로에서 양방향으로 이동 가능하므로, graph를 만들 때 양방향 정보를 모두 저장했습니다 (2) 마지막에 답을 구할 때 주어진 K 이하의 시간이 걸리는 마을의 개수를 세서 반환했습니다. import heapq def solution(N, road..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2가지 수정사항을 제외하고 플로이드 워셜 구현 코드를 그대로 활용했습니다. (1) 시작 도시와 도착 도시를 연결하는 노선이 여러 개일 수 있다고 했으므로, 여러 개의 노선 중 최솟값만 저장하도록 수정해주었고, (2) 마지막에 결과를 프린트할 때 INFINITY 대신 0을 프린트하도록 수정했습니다. import sys INF = int(1e9) # 입력 받아오기 inputs = list(map(in..