최단경로 검색 결과

해당 글 4건

[Programmers] Lv3. 부대복귀 | C++

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 다익스트라 알고리즘을 활용하여 풀었습니다. 목적지(Destination)를 시작점으로 하여 각 지역에 대한 최단 거리 배열을 구하고, 출발지(source)들에 해당하는 값들을 answer 배열에 담아주었습니다. 만약 어떤 출발지의 최단 거리 값이 초깃값과 같다면, 그 지역은 못 간다는 의미이므로 -1을 담아주면 되구요. 또한, 모든 지역 간의 이동 비용이 1이므로, 우선순위 큐 대신 일반 큐를 활용하여 시간을 줄였습니다. ✏️소스 코드 및 결과 #include #include ..
🤖Algorithm/Programmers 2024. 1. 13. 11:27

[BOJ] 11779번 | 최소비용 구하기 2 (C++)

🔗문제 보러가기 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🧑‍💻풀이 과정 기본적인 틀은 다익스트라 알고리즘인데, 최단 경로에 해당하는 각 도시들 번호를 어떻게 저장할 지가 문제였습니다. 분기가 이루어지는 각 경로마다 자기가 거쳐 온 도시 정보를 가지고 있을까 생각했다가, 메모리가 너무 많이 들 것은 물론 복사 비용이 만만치 않을 것 같아 포기했습니다. 그래서 결국 다른 분의 풀이를 참고했는데, 배열을 통해 이전 노드로 가는 길을 추적하는 참신한 방법을 사용하여 푸셔서 놀랐..
🤖Algorithm/BOJ 2023. 12. 20. 15:31

[BOJ] 1916번 | 최소비용 구하기 (C++)

🔗문제 보러가기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🧑‍💻풀이 과정 얼마 전에 다익스트라 알고리즘(Dijkstra Algorithm)을 공부했었으니, 머릿 속에서 인출하는 연습을 위해 비슷한 유형의 문제를 하나 풀어봤습니다. 우리 말이 어려운 건지, 제가 멍청한 건지 모르겠지만 매번 헷갈리는 것 같아요... 그래서 연습장에 그림 그려가며 풉니다. ( "distances[v] vs distances[u] + nextCost" 👉🏻 이게 젤 헷갈립니다. ) 알고리즘은..
🤖Algorithm/BOJ 2023. 12. 13. 18:45

[BOJ] 13549번 | 숨바꼭질 3 (C++)

🔗문제 보러가기 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🧑‍💻 풀이 과정 최단 경로 알고리즘을 연습 중에 있어, 저는 다익스트라 알고리즘으로 풀었습니다. (비용에 음수가 없기 때문) 시작 위치는 N, 도착 위치는 K로 주어집니다. N에서 i번째 노드로 가는 데에 드는 최소 시간을 저장하는 배열, times를 선언합니다. 범위가 0 ~ 100,000이니, 이 범위를 포함할 수 있는 만큼의 크기로 선언 후, 무한대 값으로 초기화합니다. times[N] = 0 으로 초기..
🤖Algorithm/BOJ 2023. 12. 6. 23:00