본문 바로가기

백준

[BOJ] 백준 [1303] 전쟁 - 전투 JAVA
알고리즘,PS/백준 2021. 8. 21. [BOJ] 백준 [1303] 전쟁 - 전투 JAVA 문제 풀이 1. dfs 탐색으로 같은 문자인 경우에만 진행하도록 함2. dfs 호출될때 마다 cnt 카운트 수 1씩 증가3. 한 무더기(?) dfs 탐색 끝났을 때 , 그 진영무리의 위력값 cnt*cnt 을 합산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.util.*; import java.io.*; public class Main{ static int w,h,cnt,white,blue; static char[][] map;..
[BOJ] 백준 [14888] 연산자 끼워넣기 JAVA
알고리즘,PS/백준 2021. 8. 20. [BOJ] 백준 [14888] 연산자 끼워넣기 JAVA 문제 풀이 이 문제는 재귀적 완전탐색(DFS) + 백트래킹 문제이다.연산자를 차례대로 방문하면서 끼워넣어 완전한 식과 그에대한 total 값을 낸 다음 , 사용하였던 연산자 개수를 회복하면서 다른 순서 방식을 통해 다시 반복하는 식으로 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 import java.util.*; import java.io.*; public class Main{ static int N; static int[] arr; st..
[BOJ] 백준 [1068] 트리 JAVA
알고리즘,PS/백준 2021. 6. 15. [BOJ] 백준 [1068] 트리 JAVA 문제 풀이 생각보다 간단한 문제이다 . 끊어질 노드를 C 라고 하자. 그래프를 ArrayList 배열로 만든 뒤 끊어질 노드'C'의 위치까지 처음부터 다 받아서 그래프를 단방향으로 연결할 때 C가 나오면 연결을 안 해주면 끝. root 부터 DFS 돌리면서 ArryList의 size가 0이면 leaf 노드이다. 입력 노드'e' 를 받을때 3가지의 경우로 나눌 수 있는데 1. e 가 root 일때 => e == -1 2. e 가 끊어질 노드 'C' 이거나 연결하려는 노드의 부모노드가 'C'일때 => ( e==C || i ==C ) 3. 그외 경우엔 단방향 연결 단방향으로 연결이 완성된 그래프를 root 부터 DFS 재귀호출을 이용하여 자식이 없는 노드를 카운트하면 끝. 이때 , 끊어질 노드 'C'가 roo..
[BOJ] 백준 [1937] 욕심쟁이 판다 JAVA
알고리즘,PS/백준 2021. 6. 14. [BOJ] 백준 [1937] 욕심쟁이 판다 JAVA 이 문제는 DFS + DP 문제이다. 여기서 DP는 최대 생존가능일 수를 기록. 기본적으로 , 입력을 map으로 받았을때, 다음 이동해야 하는 방향의 값이 지금의 값보다 더 커야한다. 즉 , map[y][x] < map[nextY][nextX] 가 성립 해야 한다. 그리고 탐색했던곳을 중복탐색하는 것을 막기위해 메모이제이션 기법으로 dp를 바로 반환해주는것이 핵심이다. 그렇지 않으면 시간초과 발생. if(dp[y][x] != 1) return dp[y][x]; dfs로 탐색했을때 , 현재 기록된 생존가능일 수 보다 더 오래 살 수 있으면 갱신. dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]); 처음에 바로 떠 올리기엔 쉽지 않은 문제이다. 12345678910111..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바