minjoott-dev 님의 블로그

https://www.acmicpc.net/problem/1238  문제 파악주어진 주요 정보/입력값입력값: 학생 수 N, 단방향 도로의 수 M, 파티 장소 X, M개의 도로 정보 (시작점 from, 끝점 to, 이 도로를 지나는데 필요한 소요시간 time)N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다.해결해야 하는 문제/출력값출력값: N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간 문제 풀이Dijkstrapackage main.java.Backjoon;import java.io.BufferedReader;import java.io.IOEx..

https://school.programmers.co.kr/learn/courses/30/lessons/118669  문제 파악주어진 정보/입력값등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있다.휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스를 intensity라고 부른다.당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다. 당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 한다.입력값XX산의 지점 수 n각 등산로의 정보를 담은 2차원 정수 배열 paths출입구들의 번호가 담긴 정수 배열 gates산봉우리들의 번호가 담긴 정수 배열 sum..

https://leetcode.com/problems/path-with-maximum-probability/description/  문제 파악주어진 정보/입력값n개의 노드를 가진 무방향 그래프 edges이 주어진다.edges[i] = [a, b]가 주어져 a와 b를 연결하는 무방향 간선이 표현될 때, 해당 간선을 순회하는 성공 가능성을 가리키는 succProb[i]이 같이 주어진다.해결해야 할 문제 start 노드와 end 노드가 주어질 때, start에서 end로 가는 길 중 가장 높은 가능성을 가진 길을 찾아내어 그 성공 가능성을 return하라.만약, start에서 end로 가는 길이 없다면, 0을 return하라.소숫점 다섯번째 자리까지 return하라. 문제 풀이Dijkstrapackage ma..

https://leetcode.com/problems/network-delay-time/description/  문제 파악주어진 정보1부터 n까지 라벨링 된 n개의 노드가 있는 네트워크 timestims[i] = (ui, vi, wi) → ui에서 vi 노드까지 신호를 보내는데 wi 시간이 걸린다.목표k노드로부터 n개의 모든 노드가 신호를 받는데 걸리는 최소 시간단, n개의 모든 노드가 신호를 받는 것이 불가능하다면 -1을 반환 문제 풀이Dijkstra (다익스트라)package main.java.LeetCode;import java.util.*;class NetworkDelayTime { public int networkDelayTime(int[][] times, int n, int k) { ..

https://leetcode.com/problems/is-graph-bipartite/description/  문제 파악n개의 노드를 가진 무방향 그래프가 주어진다. 각 노드는 0부터 n-1까지 번호가 매겨져 있으며, graph[u]는 노드 u와 인접한 노드들의 배열을 의미한다.주어진 그래프가 이분 그래프(bartite)인지 여부를 return하라.  문제 풀이그래프를 순회하면서 노드를 두 개의 그룹으로 나눌 수 있는지 확인해야 한다.DFS 또는 BFS를 사용하여 탐색하면서 그룹을 구분하면 된다.BFSclass Solution { public boolean isBipartite(int[][] graph) { int n = graph.length; boolean[] visi..