본문 바로가기

Java53

[백준 Gold 5] 2589 보물섬 - Java 문제링크 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근 과정 : 임의의 육지 2개를 고르고, 그 사이의 최단거리가 가장 긴 거리를 탐색하는 문제이다. 육지 하나하나 모두 BFS 해서 최장 거리를 탐색하는 완전탐색 방법으로 풀이할 수 있다. ++ 한 번 거리가 측정된 경로는 다시 탐색하지 않고 사용하는 것이 시간을 줄일 수 있는 포인트.. 이 부분에 대해서는 좀 더 고민이 필요하다. 소스 코드 및 결과 : package BOJ; /* 보물.. 2021. 12. 29.
[백준 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.
[백준 Gold 2] 4195 친구 네트워크 - Java 문제링크 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 접근 과정 : 익숙한 유형이라고 생각했다. 노드의 부모를 알 수 있는 자료구조와, 해당 노드가 부모인 그룹의 수를 저장하는 자료구조를 이용해서 풀이했다. 보통 익숙한 문제에서는 노드를 숫자로 주기때문에, 2개의 배열을 이용해서 쉽게 풀 수 있다. 해당 문제는 String값으로 노드가 주어졌고, 총 몇명의 친구가 주어지는지 확실하지 않았다. 그래서 HashMap으로 노드의 아.. 2021. 12. 28.

티스토리툴바