다익스트라

📖 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• 다익스트라필요 자료구조- (도착지, 거리) 정보 저장용 인접 리스트- a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열- 다익스트라용 우선순위 큐 . a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열을 최댓값 (200 * 10만 +1)으로 설정한다.. a,b,s에서 시작해서 각 점들까지의 최단 거리를 구하는 다익스트라를 총 3번 실행한다.  - 현재 번호와 연결된 점들을 지나면서, 현재 연결된 점과 다음 연결된 점까지의 거리를 더한 값이 다음 연결된 ..

📖 문제   프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• BFS필요 자료구조- 인접 리스트- 1차원 최단 거리 배열 (destination으로부터의 최단 거리를 나타냄) 1. 인접 리스트 그래프 graph에 길 정보를 저장한다.2. 최단 거리 배열을 모두 최댓값으로 저장한다.3. 시작점 destination부터 BFS를 진행하며 최단 거리 배열을 채운다.for(int next : graph[now]) { if(dist[now] + 1    🔺 코드1. List>를 활용한 풀이123456789101..

📖 문제 https://www.acmicpc.net/problem/5972   💡  풀이 방식• 다익스트라 전형적인 다익스트라 문제다,,- 최소 여물 비용 배열을 모두 5만*1000 + 1 이상의 큰 값으로 채운다.- 그래프 정보를 양방향으로 입력받는다.- 시작점 1부터 목적지 N까지 최소 비용으로 이동하도록 다익스트라를 진행한다.  🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778import java.util.*;import java.io.*; public class Main {..

📖 문제 https://www.acmicpc.net/problem/17396   💡  풀이 방식• 다익스트라필요 자료구조- 시야에 보이는지 여부 나타내는 1차원 boolean형 배열- 그래프 인접 리스트- 1 ~ N-1번 분기점이 까지 0번째 분기점까지 가는 데 걸리는 최소 시간 배열 (long형)- 분기점 별 방문 표시를 나타내는 1차원 boolean형 배열  1. 각 분기점이 적의 시야에 보이는지 나타낸다.sight = new boolean[N];st = new StringTokenizer(br.readLine(), " ");for(int i = 0 ; i   2. 1 ~ N-1번 분기점이 까지 0번째 분기점까지 가는 데 걸리는 최소 시간 배열을 모두 최댓값인 Long.MAX_VALUE로 초기화한..

📖 문제 https://www.acmicpc.net/problem/1504   💡  풀이 방식• 다익스트라필요 자료구조- 인접 배열 리스트- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열- N개의 각 정점에 대한 boolean형 방문 표시 배열- (목적지, 거리) 정보를 저장하는 객체  1. E개의 입력을 받으며 두 정점 간 거리 정보를 양방향으로 저장한다.2. 꼭 지나쳐야 하는 두 정점 v1, v2를 입력받는다.3. ① 경로 1 > v1 > v2 > N을 지날 때의 최단 거리와, ② 경로 1 > v2 > v1 > N을 지날 때의 최단거리를 계산한다. (다익스트라)4. 두 최단 거리가 모두 최댓값인 INF보다 크거나 같으면, 경로가 없는 것이므로 -1을 출력하고, 그게 아니라면 경로 1..

📖 문제 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 💡 풀이 방식 • 다익스트라 (우선순위 큐) 최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다. class Node implements Comparable { int x, y, w; public Node(int x, int y, int w) { this.x = x; this.y = y; this.w = w; } @Override public int compareTo(Node n) { // 💥 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 플로이드 와샬 N 크기가 크지 않아서 플로이드 와샬을 사용했다. i번 마을에서 j번 마을까지 이동 가능한지 확인하기 위해, 1부터 N까지 중간 지점 k의 (i,k)를 연결하는 경로가 존재하고, (k,j)를 연결하는 경로가 존재한다면 i에서 j번 마을로 배달 가능하다. dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

📖 문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 💡 풀이 방식 • 다익스트라 필요 자료구조 - 지름길 정보 저장할 Road 객체 (지름길 시작 위치, 지름길 도착 위치, 지름길 길이) - 지름길 객체 정보 저장할 Road형 배열 - 최단 거리 저장할 int형 배열 . (시작점,도착점,거리)를 저장하는 Road를 생성한다. . Road형 배열에 객체 정보를 저장한다. . 0부터 다익스트라를 진행한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 import java.util.*; impor..