본문 바로가기

Algorithm/Dijkstra

 (12)
(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와 헷갈리지 않도록 잘..

티스토리툴바