본문 바로가기

Algorithm/Dijkstra

 (14)
(C++) - 백준(BOJ) 1238번 : 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 i번 친구가 x마을로 가는데 걸리는 최소 시간과 x마을에서 i가 출발해 i마을에 도착하는데 걸리는 최소 시간의 합이 오고 가는데 거리는 총 소요시간이므로 다익스트라로 해당 값을 구해 최댓값을 출력해주면 됩니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pii = pair; i..
(C++) - 프로그래머스(2017 카카오 코드 본선) : 튜브의 소개팅 programmers.co.kr/learn/courses/30/lessons/1839 코딩테스트 연습 - 튜브의 소개팅 3 3 150 [[0, 2, 99], [100, 100, 4], [1, 2, 0]] [4, 103] 4 6 25 [[0, 1, 1, -1, 2, 4], [-1, 7, 2, 1, 5, 7], [-1, 1, -1, 1, 6, 3], [-1, 1, -1, -1, 7, 0]] [8, 15] 5 5 12 [[0, 1, 1, 1, 1], [9, 9, 9, 1, 9], [1, 1, 1, 1, 9], [1, 1, 5, 9, 9], [1, 1, 1, 1, 0]] [12, programmers.co.kr 다익스트라 문제였습니다. 풀이방법 0,0부터 시작해 s를 초과하지 않으면서 가장 짧은 경로를 찾아야 ..
(C++) - 백준(BOJ) 14496번 : 그대, 그머가 되어 www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 > b; cin >> n >> m; for(int i = 1; i > u >> v; graph[u].push_back(v); graph[v].push_back(u); } cout
(C++) - 백준(BOJ) 1261번 : 알고스팟 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라로 푼 문제였습니다. 풀이방법 1. nx행,ny열에 도착했을 때 부수는 최소 벽의 개수를 저장할 dist배열을 선언해 큰 값 0x3f3f3f3f로 초기화해줍니다. priority_queue를 이용해 항상 왼쪽 위 정점을 우선으로 볼 수 있도록 합니다. 2. nx행 ny열이 벽인 경우에는 벽을 부숴야하는지를 확인해줍니다. 현재지점(x,y)에서 nx,ny로 도착하기 위해서는 벽을 부숴..
(C++) - 백준(BOJ) 1916번 : 최소비용 구하기 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 1. 도시 사이에 연결된 간선과 가중치를 vector 자료구조 graph변수에 저장합니다. 2. 출발도시부터 i도시까지의 최소비용을 저장할 변수 dist배열 선언 후 모든 값을 큰수 INF로 초기화 합니다. 3. dijsktra 함수를 실행합니다. 3-1. dist[startCity] = 0 입니다. 출발도시의 최소비용은 0이기 때문입니다. 3..
(C++) - 백준(BOJ) 18352번 : 특정 거리의 도시 찾기 www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 기본 다익스트라 문제였습니다. 풀이방법 1. 입력 및 초기화 : 단방향 그래프입니다. 도시 u,v가 있을 때 u -> v로 간다면 가중치가 1이라고 생각합니다. 또한 최단거리를 구해야 하므로 dist배열을 선언한뒤 n까지의 도시까지 나올 수 없는 큰 값으로 초기화해줍니다. * 도시의 번호가 1부터 시작하므로 index와 헷갈리지 않도록 잘..

티스토리툴바