dfs
-
[JAVA] 백준 2213 트리의 독립집합알고리즘 공부/문제 풀이 2021. 11. 9. 21:32
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net - 어려웠다.. 결국 블로그의 도움을 받아 해결하였다 - 트리의 구조 -> 어느 정점이든 루트가 될 수 있다 -> 편의상 1번 정점을 루트로 생각하고 1번 노드부터 dfs 탐색을 진행한다 - 현재 접근한 노드를 포함할 때/포함하지 않을 때의 최대 독립 집합의 가중치를 구해본다 => memo[N][2] - 현재 노드를 집합에 포함한다면, 인접한 다음 노드는 포함되지 ..
-
[JAVA] 백준 16168 퍼레이드알고리즘 공부/문제 풀이 2021. 11. 2. 10:08
https://www.acmicpc.net/problem/16168 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer..
-
[JAVA] 백준 2638 치즈알고리즘 공부/문제 풀이 2021. 10. 7. 22:05
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..
-
[JAVA] 백준 17471 게리맨더링알고리즘 공부/문제 풀이 2021. 10. 6. 11:28
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { static int N, total=0, min = Integer.MAX_VALUE; static int[] people; static ArrayList[] graph; public static void main(String[] args) throws Exception { BufferedReader br = new ..
-
[JAVA] SWEA 탈주범 검거알고리즘 공부/문제 풀이 2021. 9. 30. 21:14
문제 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import java.util.*; import java.io.*; public class Solution { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for(int t=1; t
-
[JAVA] 백준 17472 다리 만들기2알고리즘 공부/문제 풀이 2021. 9. 17. 10:59
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제의 설명은 링크와 문제 분석을 참고해주세요 풀이 해결 전략은 문제를 풀며 적은 내용으로 실제 작성한 코드와 상이할 수 있습니다. 변경된 부분은 왜 변경했는지 풀이 후기에 적어 놓았으니 참고 바랍니다! 코드 import java.util.*; import java.io.*; public class Main { static int N, M; static int[][] map;..