최단경로

알고리즘 문제) BOJ 5944. Apple Delivery 링크 : https://www.acmicpc.net/problem/5944문제 요약C개의 길과 P개의 목초지가 존재이때, 각 길에는 거리비용이 존재PB에서 시작해 PA1와 PA2 목초지로 방문하려고 할 때, 이동해야할 최소 거리는?시간 제한2초입력C, P, PB, PA1, PA21 ≤ C ≤ 20만1 ≤ P ≤ 10만모든 거리의 합은 20억을 초과XC개의 줄에 두 목초지 번호와 그 사이 거리가 주어짐출력두 목초지를 방문할 때 이동할 최소 거리는?접근법PB에서 PA1과 PA2 방문을 위한 최소 경로를 구해야하므로 총 2가지 경로가 있을 수 있다PB → PA1 → PA2PB → PA2 → PA1따라서, PB ~ PA1 / PB ~ PA2 / PA1..

알고리즘 문제) BOJ 2176. 합리적인 이동경로 링크 : https://www.acmicpc.net/problem/2176문제 요약그래프의 한 정점 S에서 다른 한 정점 T로 이동이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로이러한 경로는 최단경로가 아닐 수도 있다그래프가 주어졌을 때 가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성시간 제한2초입력첫째 줄에 정점의 개수 N(1 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, CA번 정점과 B번 정점이 길이 C(0 두 정점은 최대 한 개의 간선으로만 연결간선은 방향성이 없다출력첫째 줄에 답을 출력한다.답은 2147483647을 넘지 않는다.접근법합리적인 경로라는 의미는?dist(a,b) : 정점 a에서 ..

알고리즘 문제) BOJ 31589. 포도주 시음 링크 : https://www.acmicpc.net/problem/31589문제 요약N종류의 포도주가 존재하며, 각각 맛을 지니고 있다이때, 첫 잔을 마실 때는 포도주 본연의 맛을 느끼지만그 이후부터 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 0의 맛을 느끼며맛없는 포도주를 마시다가 맛있는 포도주를 마시면 두 포도주의 맛의 차이만큼 느낀다이때 K종류의 포도주만 마신다 했을 때, 최대로 느낄 수 있는 맛을 구해라시간 제한1초입력포도주의 수 N, 마셔야할 포도주 수 K1 ≤ K ≤ N ≤ 30만N개의 포도주 맛 Ti가 주어진다1 ≤ Ti ≤ 10억출력맛의 합의 최댓값은?접근법순차적으로 먹게 될 경우 맛의 차이만큼 먹게된다.이때, 순차적으로 먹게 될 경우 ..

알고리즘 문제) BOJ 2458. 키 순서 링크 : https://www.acmicpc.net/problem/2458문제 요약1번~N번의 학생들이 존재N명의 학생들은 모두 키가 다름학생들의 키를 비교한 결과가 주어질 때 자신의 키가 몇 번째인지 알 수 있는 학생은 모두 몇 명일까?시간 제한1초입력학생들의 수 N, 두 학생 키를 비교한 횟수 M2 ≤ N ≤ 5000 ≤ M ≤ N*(N-1)/2다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 a b가 주어짐a가 b보다 키가 작다를 의미출력자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력접근법키가 몇 번째인지 알 수 있다는 의미를 그래프 관점에서 다시 해석해보자면(유방향 그래프)나를 제외한 다른노드와 연결되어있는지 파악하면 된다..

알고리즘 문제) BOJ 1613. 역사 링크 : https://www.acmicpc.net/problem/1613문제 요약알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계를 찾아라시간 제한1초입력사건의 개수 N, 알고 있는 전후 관계 개수 KN : 400이하 자연수K : 4만 이하 자연수K개 줄에 사건의 전후 관계를 알고 있는 두 사건 번호가 주어짐a ba는 보다 먼저 발생사건의 전후 관계를 알고 싶은 사건 쌍의 수 SS : 5만 이하 자연수S개 줄에 서로 다른 두 사건 번호가 주어짐출력S개 줄에 걸쳐앞에 있는 번호의 사건이 먼저 일어났으면 -1뒤에 있는 번호의 사건이 먼저 일어났으면 1유추할 수 없으면 0을 출력접근법처음에 위상정렬로 풀려고 했는데, 생각해보니 나중에 알고 ..

알고리즘 문제) BOJ 1082. 방번호 링크 : https://www.acmicpc.net/problem/1082코드import java.io.*;import java.util.*;/*[문제요약]스타트링크가 입주한 사무실은 방 번호 직접 정할 수 있음이떄, 1층 문방구에서 파는 숫자 구매해야함필요한 금액은 M원각 숫자 i의 가격은 Pi고 숫자는 0부터 N-1까지 존재같은 숫자 여러개 구매 가능,방 번호는 0을 제외하고 0으로 시작 불가N이 주어지고 다음 줄에P0... PN-1이 주어짐마지막줄에는 MN 은 1~10Pi는 1~50M은 1~50첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력(가능한 입력만 주어짐)최대 50자 가능함 */public class Main { stati..

알고리즘 문제) BOJ 13911. 집 구하기 링크 : https://www.acmicpc.net/problem/13911코드import java.io.*;import java.util.*;/*[문제요약]- 맥세권 : 집 ~ 맥도날드 최단 거리 x이하- 스세권 : 집 ~ 스타벅스 최단 거리 y이하- 원하는 집 : 맥세권과 스세권을 만족하는 집 중 최단 거리 합이 최소정점 개수 : V 3 ~ 1만도로 개수 : E 0 ~ 30만E개의 줄에 각 도로를 나타내는 세 개의 정수 u, v, w가 주어짐 w : ~1만 정점 u v 사이에 가중치 w인 도로가 존재 두 정점 사이에는 여러 간선이 존재 가능E+2번째 줄에는 맥도날드 수 M, 맥세권 조건 x가 주어짐 x : ~1억다음 줄에 M개의 맥도날드 정점 번호..