깊이우선탐색4 [백준 Gold 4] 3584 가장 가까운 공통 조상 - Java 문제링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 접근 과정 : 부모 - 자식 관계가 주어지고 두 노드가 주어졌을 때, 그 두 노드의 가장 가까운 공통 조상을 찾으면 된다. 저장한 부모-자식 관계를 따라서 노드 A의 조상을 체크한다. DFS로 B의 조상을 탐색하면서 A의 조상체크가 되어있는 조상을 발견하면 리턴한다. 소스 코드 및 결과 : package BOJ; /* 가장 가까운 공.. 2022. 1. 2. [백준 Gold 3] 2146 다리 만들기 - Java 문제링크 : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 접근 과정 : DFS를 통해 같은 대륙은 같은 번호를 붙여서 구분. 대륙을 탐색할 때, 대륙은 Queue에 좌표와 대륙 번호를 저장 (BFS 때 이용하기 위해) 어떤 대륙에서 출발하여, 다른 번호의 대륙을 만날 때, 그 거리를 반환하는 BFS 구성 한칸에서 시작하는 DFS를 하는 것이 아니라, 모든 대륙을 담은 Queue로 한번에 BFS를 시행 방문체크는 int[][]에 비트마스킹을 통해 .. 2021. 12. 28. [백준 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. [백준 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. 이전 1 다음
