개발하는 사막여우

https://www.acmicpc.net/problem/12834 12834번: 주간 미팅 첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): min_dis = [float("inf") for _ in range(v+1)] q =[] hq.heappush(q,[0,start]) min_dis[start] = 0 while q: ..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 소스코드 import sys import heapq as hq from collections import deque input = sys.stdin.readline def dijkstra(): q = [] min_dis = [float('inf') for _ in range(n)] hq.heappush(q,[0,s]) min_dis[s] = 0 while q: cur..

https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 소스코드 풀이 ★ 집에서 목표지점으로 갈 때와 목표지점에서 고려대학교로 갈 때의 조건이 달라서 처음엔 함수를 2개 만들어야하나 싶었습니다. 근데 조건을 보면 집과 고려대학교의 높이가 모두 1이기 때문에 역으로 생각해보면, 각각의 지점에서부터 목표까지 가는 방향의 높이는 모두 증가하기에 집 -> 목표 조건 성립, 목표 -> 고려대학교 조건이 성립합니다. ★ 그렇기에 다익스트라를 구현하면서 ..

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 소스코드 풀이 ★ 전형적인 다익스트라입니다 !!

https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 소스코드 풀이 ★ 그래프가 주어졌을 때, 가로 세로 방향으로 누울 수 있는 모든 자리를 구해줘야 합니다. 예를 들어 가로로 ..X..이 주어졌을 때 누울 수 있는 공간은 총 2개입니다 !!

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 소스코드 풀이 ★ 다익스트라를 통해 예은이가 떨어진 위치에서 수색할 수 있는 범위를 찾아줍니다. 그 후 그 범위 안에 있는 위치들이 가지고 있는 아이템의 개수의 합을 구해주면 됩니당 :)

https://www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 소스코드 풀이 ★ 도로 건설을 시작하는 시점 즉, 맨 왼쪽의 맨 위쪽 좌표의 값이 -1일 경우 ( 도로 건설을 아예 시작하지 못하는 경우)도 고려해줘야 합니당 !!! :)

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): min_dis = [int(1e9)] *(n+1) q = [] hq.heappush(q,[0,start]) min_dis[start] = 0 while q: cur_dis,cur_node = hq.heappop(q) if min_dis[cur_node..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 소스코드 풀이 ★ b가 감염되면 s초 이후 a가 감염되는 형태이기 때문에 그래프를 만들 때 b -> a로 향하는 간선을 만들어줘야 합니다 ! ★ 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력해주는데, 감염이 이루어질 때마다 이전에 걸렸던 시간과 비교하여 최댓값을 찾아줍니다. ★ 기존에 min_dis 배열을 int(1e9)로 초기화 해뒀기 때문에 감염되지 않은 컴퓨터들은 int(1e9)가 값이고, 감..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 소스코드 풀이 ★ 주어진 두 정점을 반드시 거치면서 최단 경로로 이동해야 하기 때문에 1부터 n까지 이동할 수 있는 방법은 총 두가지입니다. 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 위 두 케이스를 통해 경로를 도출하고, 그 중 최단경로를 출력해줍니다 :)