minjoott-dev 님의 블로그

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

https://leetcode.com/problems/keys-and-rooms/  문제 파악0부터 n-1까지 번호가 매겨진 n개의 방이 있으며, 0번 방을 제외한 모든 방은 잠겨 있다.입력으로 주어지는 배열 rooms에서 rooms[i]는 i번 방을 방문했을 때 얻을 수 있는 키들의 집합을 의미한다.이 키들을 사용하여 모든 방을 열고 방문할 수 있는지 여부를 return하라.  문제 풀이BFSDFSBFSclass Solution { public boolean canVisitAllRooms(List> rooms) { Queue queue = new LinkedList(); boolean[] visited = new boolean[rooms.size()]; vis..