dfs7 [백준 Gold 2] 17472 다리 만들기 2 - Java 문제링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 접근 과정 : 크게 4개의 과정으로 문제를 해결하려고 했다. input() : 입력을 받는 단계. N,M을 입력받고 그에 따라 Map[][] 입력받는다. defindLand() : 섬을 정의하고 구분한다. 섬에 번호를 붙여 구분한다. serarchBridge() : 섬들 사이에 연결할 수 있는 모든 다리를 구한다. minBridges() : 앞서서 구한 다리들을 .. 2022. 1. 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. [백준 Silver 2] 2644 촌수 계산 - Java 문제링크 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 접근 과정 : 두 사람간의 촌수를 계산하는데, 두 사람의 공통 조상 중 가장 가까운 공통 조상을 찾아야 한다. 즉, 공통 조상이 여럿 있을 수 있다는 것을 인지해야 한다. (난 이 부분을 인지하지 못해 처음에 실패했다.) 나와 친척의 공통조상은 조부모, 증조 조부모, 고조 조부모가 될 수 있기 때문에!!!! 가장 가까운 공통 조상을 찾아야 한다!! 먼저 입력으로 주.. 2021. 12. 29. [백준 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. 이전 1 2 다음
