본문 바로가기

그래프 탐색45

[백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다.  메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12.
[백준] 28071: 승형이의 사탕 사기 - JAVA https://www.acmicpc.net/problem/28071 풀이dp문제이다. M개의 사탕 상자를 가져갈 수 있고, 사탕 개수의 총 합은 K로 나누어 떨어져야 한다. 상자의 개수와 나머지에 따라 dp배열을 생성한다. dp[i][j]에서 i를 상자의 개수, j를 나머지라고 하면 dp[i][j]의 값은 i-1개의 상자에서 "j - 현재 사탕상자의 사탕 개수"일때의 dp값을 이용하여 갱신한다. "j - 현재 사탕상자의 사탕 개수"가 음수가 되면 안되기 때문에 Math.floorMod연산을 사용했다. dp배열을 채운 후 나머지가 0인 경우 중 최댓값을 구한다.  메모리: 15152KB시간: 424ms언어: Java 11import java.io.*;import java.util.*;public class.. 2024. 5. 11.
[백준] 21738: 얼음깨기 펭귄 - JAVA https://www.acmicpc.net/problem/21738 풀이그래프 탐색 문제. 펭귄이 얼음 위에 올라가있는데 떨어지지 않으려면 연결된 지지대 얼음 2개가 필요하다. 최소한의 얼음만 남기고 얼음을 깨야한다. 펭귄의 위치로부터 탐색한다. 먼저 발견한 얼음이 가깝다는 것이므로 먼저 발견한 2개의 지지대 얼음을 제외한 나머지 얼음은 깨는 것으로 한다.  메모리: 152136KB시간: 696ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, S, P, ans; static ArrayList> list; public static void main(String[] args) throws IOE.. 2024. 5. 11.
[백준] 2636: 치즈 - JAVA https://www.acmicpc.net/problem/2636 풀이구현 + 그래프탐색문제였다. 공기와 맞닿아있는 치즈는 한 시간이 지나면 녹는다. 치즈 내부에 구멍이 있을 수 있는데 외부 공기와 연결되어있지 않으면 치즈를 녹이지 않는다. 판의 가장자리는 치즈가 놓이지 않으므로 (0,0)은 항상 공기이다. (0,0)부터 시작하여 BFS탐색을 통해 공기면 Quque에 넣어주고, 치즈면 녹인다. ✔️참고 1.static int[] dr = { 1, -1, 0, 0 };static int[] dc = { 0, 0, 1, -1 }; 2.static int[][] vector = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };사방탐색을 할 때 1번 코드보다 2번 코드로 하는 것.. 2024. 5. 11.
[백준] 20869: 김밥천국의 계단 - JAVA https://www.acmicpc.net/problem/28069 풀이bfs와 dp로 접근할 수 있는 문제.  bfs메모리: 57612KB시간: 204ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.n.. 2024. 5. 11.

티스토리툴바