개발조아

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 최소 비용으로 목적지에 도달해야하므로 다익스트라로 해결했다. 같은 방향으..

문제 링크 : https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 처음 풀이가 맞았는데 오타 때문에 지우고 다시 풀다가 오타를 발견하고 원래코드로 돌아와 푼 바보같은 문제였다. 하지만 결국 시간초과랑 싸운 문제이다. 알고리즘은 간단하다. 우선 최단경로를 구해야하므로 다익스트라를 사용했다. 그리고 각 노드를 방문했을 때의 상태가 달라야한다. 상태는 도로를 포장한 개수이다. 다음 도로를 포장하고 갈지 아니면 그냥 갈..

문제 링크 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 처음에는 문제의 조건이 좀 어려웠었다. 하지만 결국 최소한의 비용으로 최소한의 개수로 연결해라인데 결국 다익스트라를 사용하면 된다. 다익스트라로 각 점마다의 최단경로를 구할 수 있다. 하지만 경로를 저장해야한다. 그래서 나는 비용과 연결된 이전 노드를 저장했다. 2번 노드에서 3번노드로 연결되어있고 비용이 1이라면 배열[3] = (2,1) 이런식으로 저장된..

문제 링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 기본적인 다익스트라 문제이다. 우선순위 큐를 이용하여 잃은 금액이 최소인 것을 우선적으로 빼서 진행하면 된다. from sys import stdin from heapq import heappush, heappop input = stdin.readline dx = [-1,1,0,0] dy = [0,0,-1,1] INF = 9876543210 def solv(): p..

문제 링크 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 노드에서 출발하여 정해진 가중치 이내로 갈 수 있는 노드들이 가지고 있는 값의 합의 최대값을 구하는 문제이다. 모든 노드에서 각 노드로 최단거리를 구해서 그 길이가 m 이하인 것들의 아이템수의 합을 구하고 그중 최대값을 구하면 된다. 모든 노드에 대해서 최단거리는 플로이드와샬과 다익스트라로 해결할 수 있다. 해당 문제는 노드의 개수가 최대 100개 이므로 플로이드와샬로 해결 가능하다...

문제 링크 : https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 문제를 잘 이해를 못해서 좀 고민했다. 가장 안전한 길이란 모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로이다. 이 부분에서 최솟값이 가장 큰 경로라길래 최솟값이 가장 크면 가장 작은 값인가 큰값인가 헷갈렸었다. 아주 멍청이 같은 생각이었다. 모든 점에서 나무까지의 거리 중 최소값을 찾아서 저장하고 이동 중에 이 거리가 큰값을 선택해서 가면 된다. 모든 점에서 나무까지의 거리는 BFS로 돌..