본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/벨만포드,다익스트라,MST

 (27)
[백준 / BOJ] 1967 트리의 지름 문제 출처 : www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가중치를 가진 트리가 주어진다. 이때, 트리의 지름을 구하는 문제이다. 트리의 지름은 트리의 모든 경로들중 가장 긴 경로를 말한다. (가장 긴 경로를 지름으로 하는 원을 그리면, 모든 노드들을 해당 경로안에 집어넣을수있다.) 풀이 전형적인 트리의 지름을 구하는 문제다. BFS,DFS,다익스트라 등으로 풀수있는데, 최단시간으로 답을 구하는 방법은 다익스트라라고 생각해서 다익스트라..
[백준 / BOJ] 2158 산악자전거 문제 출처 : www.acmicpc.net/problem/2158 2158번: 산악자전거 첫째 줄에 세 정수 V, R, C가 주어진다. 다음 R개의 줄에는 C개의 정수로 행렬이 주어진다. 행렬의 각 수는 -25이상 25이하의 정수이다. www.acmicpc.net R*C 행렬이 주어지고, 각 칸마다 높이가 주어진다. 현재 높이A에서 높이 B로 이동할때, 속력이 (2^(A-B))배로 변한다. (R,C) 위치에 도달하는 최소시간을 구하는 문제다. 풀이 다익스트라로 풀리는문제다. 목적지에 도달할때, 다른 경로로 뺑돌아서 (속력을 높인후) 도착하는 경우가 더 빠를수 있기때문에, 다익스트라로 풀어야한다. 구현은 일반적인 다익스트라에 속력을 계산해주는걸 추가하면된다. 주의할점이 현재 (y,x)에 도착한 도달시간이 ..
[백준 / BOJ] 1162 도로포장 문제 출처 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 도시의수 N, 도로의수 M, 포장할 도로의수 K가 주어진다. M개의 도로를 K만큼 포장할수있고, 포장한 도로의 비용은 0이될때, 최소비용을 구하는 문제다. 풀이 2206 벽 부수고 이동하기 와 비슷한 느낌의 문제였다. 다익스트라로 풀었는데, 포장횟수가 20까지밖에 안주어지므로 모든경우를 다 봐줘도 시간초과가 나지않는다. check배열을 2차원으로 만들어서, 체크..
[백준 / BOJ] 15906 변신 이동 게임 문제 출처 : www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 성호는 새로운 모바일 게임을 다운로드 했다. 성호의 캐릭터는 N*N의 위치에서 상,하,좌,우로 1칸 움직일수있는데, 이때, 캐릭터가 변신모드라면, 상,하,좌,우중 가장 가까운 워프지점으로만 갈수있다. (변신모드로 전환하는데는 t만큼의 턴이 소요된다.) 성호의 캐릭터가 목표지점까지 도달하는데 걸리는 최소한의 턴을 구하는문제다. 풀이 다익스트라로..
[백준 / BOJ] 20046 Road Reconstruction 문제 출처 : www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 � www.acmicpc.net m*n의 격자 모양의 격자가 있다. 격자의 각 칸에는 도로가 있을수도, 없을수도 있는데, 이 격자에 도로를 배치하여 (1,1)지점에서 (m,n)까지 가는 다리를 만들어야한다. 칸마다 도로를 만드는데 드는 비용은 다르다 (비용 1과 비용2가 있음) -1인 지점에는 도로를 만들지 못하고, 0은 이미 도로가 있는 곳이다. 비용을 최소한으로 사용..
[백준 / BOJ] 10423 전기가 부족해 (다익스트라) 문제 출처 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net K개의 발전소, N개의 도시, M개의 케이블수가 주어졌을때, 발전소에서 시작해서 모든도시까지 전기를 공급하는 문제다. 풀이 입력받은 발전소들을 시작지점으로해서 다익을 돌리면된다. 예를들어, 발전소가 3개일경우 다익의 시작지점은 총 3개가 된다. 코드를 짜면서 몇가지 반례?가 될수있는걸 생각해봤는데, 도시와 발전소 사이에 발전소가 존재할경우..? 발전소 N..
[백준 / BOJ] 2917 늑대 사냥꾼 문제 출처 : www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 늑대 현우는 사냥꾼을 피해서 최대한 안전한 경로로 집으로 도착해야한다. 사냥꾼은 나무뒤에 숨어있다. N*M 배열이 주어지고, 나무의 위치는 +, 현우의 위치는 V, 오두막의 위치는 J로 주어진다. 현우의 위치에서 집까지 가는 가장 안전한 경로에서 나무와 현우의 거리의 최솟값을 출력하는 문제다. 풀이 BFS를 돌려서 나무와 모든정점들에 최단거리를 저장해주고, 현우의 위치를 기준으로 다익을 돌려 가장 안전한 ..
[백준 / BOJ] 17835 면접보는 승범이네 문제 출처 : www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net N개의 도시와 도시에따른 M개의 길, K개의 면접장이 주어진다. 승범이네라는 회사에서 신입사원을 뽑을려한다. N개의 도시에 살고있는 면접 준비자들은 자신의 도시에서 가장 가까운 면접장으로 가야한다. 이때 면접장 까지의 거리가 가장 먼 도시와 그때의 거리를 출력하는 문제다. (만약 거리가 가장 먼 도시가 여러군데라면 번호가 작은 도시를 출력하면..

티스토리툴바