다익스트라

1. 개요 안녕하세요. 이 문제의 유형은 다익스트라입니다. 다익스트라란 가중치 그래프에서 임의의 정점을 출발점으로 지정해 다른 정점까지의 최단 거리를 빠른 시간 내에 구할 수 있는 알고리즘입니다. 로직 구현 자체에는 BFS와 큰 차이점은 없습니다.  문제를 해석해보시면 간선을 순서대로 하나씩 추가하다가 정점 s와 정점 t가 간선을 통해 방문할 수 있는 상태가 되면 간선 추가를 중지합니다. 그 후 추가했던 간선들의 가중치 합을 구하려고 합니다. 여기까지만 읽었다면 다익스트라를 적용할 수 있는지는 확신이 들지 않습니다. 하지만 다음 문장에 s와 t가 연결되는 시점에서 추가된 간선의 가중치 합이 최소가 되도록 추가할 간선의 순서를 조정한다고 합니다. 즉, 저희는 입력으로 주어지는 순서대로 간선을 추가할 필요가..

1. 개요 안녕하세요. 이번 문제의 유형은 2차원 배열에 다익스트라 알고리즘을 응용한 문제였습니다. 문제를 읽고 상태값을 거리 배열에 저장하는 방법을 사용하는 너비우선탐색 응용문제일 거라고 생각하고 풀이했다가 런타임 에러에 막혀 알고리즘 유형을 까고 나서야 풀이할 수 있었습니다. 무의식적으로 2차원 배열은 너비우선탐색 또는 dfs를 응용한 dp문제라고 생각하고 풀이한 것 같습니다. 이 문제를 푼 오늘이 일요일인데 우연히 문제 제목에도 일요일이 있었네요. 어쩌라고요? 그냥 그렇다고요 반박 시 니 얼굴이고요 2. 문제 풀이 우선 배열을 탐색하면서 필요한 데이터 정보를 파악해 봅시다. "쓰레기칸과 인접한 칸을 지나가는 경우", "쓰레기칸을 이동하는 경우", "현재 위치 정보 (x, y)"와 같은 정보가 필요합..

1. 문제 풀이 문제 유형은 parametric search와 dijkstra입니다. 우선 이분 탐색으로 1번 컴퓨터에서 N번 컴퓨터를 연결하는데 최대로 사용할 수 있는 금액 cost를 결정합니다. 이후 간선의 가중치 정보를 cost에 맞추어 재가공하는데 cost보다 작거나 같다면 0으로 크다면 1로 간주하여 N번 컴퓨터까지 연결하는데 cost보다 비용이 큰 케이블의 개수가 몇 개인지 구합니다. 만약 d[n]에 저장되어 있는 값이 k보다 작거나 같다면 해당 cost로 탐색이 가능하다고 간주할 수 있습니다. 2. 소요 시간 및 경과시작 시간: 15시 16분#1 제출 시간: 16시 06분67% WA원인: N번 컴퓨터를 연결 못하는 경우를 구현하지 않음#2 제출 시간: 16시 12분67% WA#3 제출 시간:..

1. 문제 풀이 문제의 유형은 다익스트라 응용입니다. 주어진 조작 방법만을 사용하여 배열을 비내림차순으로 정렬해야 합니다. 배열정보를 문자열로 저장한 다음 해쉬를 사용해 방문 배열을 만들어 다익스트라를 돌리면 풀이할 수 있습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector ..