전체 글

문제 풀이 1. 이 문제는 bfs와 같은 일반적인 그래프 탐색으로 접근하면 시간초과가 나버린다.. -> dp 문제 2. 경로의 개수는 263-1보다 작거나 같으므로 dp의 자료형을 long으로 선언 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 import java.util.*; import java.io.*; public class Main{ static int N; static int[][] map; static long[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = ..

문제 풀이 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;..

문제 풀이 이 문제는 재귀적 완전탐색(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..

문제 풀이 전형적인 크루스칼 알고리즘 풀이다. 1. Edge의 weight크기가 작은 순으로 정렬 2. Edge를 집합에 포함 시키기위해 find(x) 함수를 호출해서 parent가 같은지 확인 3. Parent가 같지 않은 Edge 한에서 Union을 호출하여 집합에 포함시킨 후 가중치 합을 반환 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 import java.util.*; import java.io.*; class Solution{ static int[] parent; static ArrayLi..

문제 풀이 이 문제에서 집어야 할 포인트는 세 가지다. 1. 3차원 visit[][][] 배열을 사용하여 열쇠를 먹을때 마다 visit[][][index++] 을 처리해줘서 열쇠 먹은시점이랑 열쇠를 안 먹은 시점이랑 분리 시키는 것. 2. BFS를 위해 집어 넣을 노드인 'Point' 에 대해 Comparable을 구현하여 열쇠를 가장 많이 먹은 시점이 우선 탐색할 수 있도록 해주는것. 3. 우선순위 큐인 PriorityQueue를 사용할 것. 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 ..

문제 풀이 이 문제에서 집어야 할 포인트는 두 가지다. 1. BFS를 활용한 우선순위 큐(PQ)를 이용하여 PQ안의 원소를 처리할 때 먼 산으로 가지 않게 하는 것. 2. 어느 위치(cur)로 갔을 때, 몇 번 만에 갔는지를 기록하여 (distance[] 배열) 무한 루프로 빠지지 않게 하는 것. => 즉 , if(distance[cur+e] > distance[cur]+ 1) { distance[cur+e] = distance[cur]+ 1; q.add(e + cur); } 이 식이 성립해야 하는데, 여기서 cur은 현재위치이고 , e 는 up 또는 down 버튼을 눌렀을 때의 증감치다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 풀이 생각보다 간단한 문제이다 . 끊어질 노드를 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..

이 문제는 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..