본문 바로가기

dfs7

[백준 Gold 3] 1937 욕심쟁이 판다 - Java 문제링크 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 접근 과정 : DFS를 통해서, forest[i][j] 에서 판다가 출발하는 경우를 모두 조사. 다만 이미 한번 조사했던 칸은 dp[i][j]에 저장된 값을 사용하여 재탐색 비용을 줄임 즉, DFS+메모리제이션으로 문제를 접근 (배열 이름만 dp....) 방문체크가 필요없는 이유 : 판다는 현재칸보다 더 큰 값의 칸으로만 이동하기 때문에 다시 같은 칸을 방문하지 않는다!! .. 2021. 12. 23.
[백준 Gold 2] 14657 준오는 최종인재야!! - Java 문제링크 : https://www.acmicpc.net/problem/14657 14657번: 준오는 최종인재야!! 첫째 줄에 문제의 수 N, 하루 풀이 시간 T가 주어진다. (2 ≤ N ≤ 50,000, 1 ≤ T ≤ 100,000) 이후 둘째 줄 부터 N-1개의 줄에 걸쳐 각 줄마다 A, B, C가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000) A와 B는 www.acmicpc.net 접근 과정 : 먼저 가장 많은 문제를 푸는 경우(트리의 지름)을 찾아야 한다.!! + 가장 많은 문제를 푸는 경우가 여러개 존재한다면, 가장 시간이 짧은 것을 찾아야 한다.!! 즉, 가장 긴 트리의 지름 중에서 가장 가중치가 적은 경우를 찾고 이를 기준으로 다시 한번 조회해서, 정확한 가중치를 찾아서 반.. 2021. 12. 21.
[백준 Silver 1] 2583 영역구하기 - Java 문제링크 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 접근 과정 : 모눈종이를 표현하는 boolean[][] map 배열 생성 입력되는 직사각형에 따라서, 해당 직사각형에 포함되는 영역을 map에 체크 모든 직사각형의 입력이 끝난 후, 모눈 종이를 순회하면서 직사각형이 아닌 영역의 개수 파악. 직사각형이 아닌 부분이 나오면, 해당 칸을 기준으로 DFS하여, 칸의 개수를 파악 영역의 칸의 개수는 List에 담고, 이를 .. 2021. 12. 16.

티스토리툴바