minjoott-dev 님의 블로그

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/longest-consecutive-sequence/description/  문제 파악정렬되지 않은 정수 배열 nums가 주어질 때, 배열의 원소들로 연속된 수열을 만들려고 한다. 만들 수 있는 가장 긴 수열의 길이를 return하라.단, 알고리즘이 O(n) 시간 내에 수행되도록 작성해야 한다.  문제 풀이HashSetclass Solution { public int longestConsecutive(int[] nums) { int answer = 0; Set hashSet = new HashSet(); for (int num : nums) { hashSet.add(num);..

http://acmicpc.net/problem/13459  문제 파악구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 보드에 있는 구멍 하나에 빨간 구슬을 구멍을 통해 빼내는 게임이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.중력을 이용해서 이리 저리 굴려서, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있으면 1, 없으면 0을 출력한다.  문제 풀이package main.java.Backjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.ut..

https://www.acmicpc.net/problem/17142 문제 파악연구소에 있는 비활성 바이러스 중 M개를 어떻게 골라서 활성 상태로 변경하여야, 가장 빠르게 모든 빈 칸으로 활성 바이러스를 전파시킬 수 있는지 알아낸다.✔️ 출력값: 모든 빈 칸에 활성 바이러스를 전파 시키는 데 걸리는 최소 시간. (단, 모든 빈 칸에 바이러스를 퍼뜨릴 수 있는 경우가 존재하지 않는다면 -1를 출력한다.)  문제 풀이Backtracking + BFSpackage main.java.Backjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class..

https://www.acmicpc.net/problem/14502문제 파악바이러스 확산을 최소화하기 위해 3개의 벽을 세울 위치를 찾아야 한다.그렇게 했을 때, 바이러스가 퍼지지 않는 안전 영역의 최대 크기를 return하라.  문제 풀이Backtracking + BFSpackage Backjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class 연구소 { static int maxSafe = 0; // answer public static void main(String[] args) throws IOException { ..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 문제 파악출발지에서 목적지까지 가는 가장 짧은 거리를 return하라.  문제 풀이그래프 문제에서 최단 거리(Shortest Path) 탐색은 BFS를 사용한다.BFSclass Solution { public int shortestPathBinaryMatrix(int[][] grid) { int n = grid.length; if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1; Queue queue = new LinkedList(); boolean[][] visited..

https://leetcode.com/problems/number-of-islands/description/  문제 파악문제에서 주어진 정보1(land)와 0(water)로 표현된 이진 그리드가 주어진다.1이 수평과 수직으로 연결된 경우 같은 섬으로 간주한다.출력섬의 개수를 return하라.  문제 풀이BFSclass Solution { public int numIslands(char[][] grid) { int count = 0; // answer Queue queue = new LinkedList(); int m = grid.length, n = grid[0].length; boolean[][] visited = new boolean[m][n]..

https://leetcode.com/problems/coin-change/  문제 파악입력coins: 동전의 종류를 담은 정수 배열amount: 목표 금액조건동전은 무한히 사용할 수 있음출력amount를 만들기 위해 필요한 최소 동전 개수 반환만들 수 없으면 -1 반환  문제 풀이BFSclass Solution { public int coinChange(int[] coins, int amount) { Queue queue = new LinkedList(); boolean[] visited = new boolean[amount + 1]; if (amount == 0) return 0; queue.add(new Entry(0, 0)); ..

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..