본문 바로가기

자바37

[백준 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 2] 4195 친구 네트워크 - Java 문제링크 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 접근 과정 : 익숙한 유형이라고 생각했다. 노드의 부모를 알 수 있는 자료구조와, 해당 노드가 부모인 그룹의 수를 저장하는 자료구조를 이용해서 풀이했다. 보통 익숙한 문제에서는 노드를 숫자로 주기때문에, 2개의 배열을 이용해서 쉽게 풀 수 있다. 해당 문제는 String값으로 노드가 주어졌고, 총 몇명의 친구가 주어지는지 확실하지 않았다. 그래서 HashMap으로 노드의 아.. 2021. 12. 28.
[백준 Gold 4] 17142 연구소 3 - Java 문제링크 : https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근 과정 : 연구소의 빈칸에 모두 바이러스가 있게 만드는 시간을 구하는 문제이다. 활성화 여부에 상관없이, 모든 칸에 바이러스가 있으면 된다.. 활성화 바이러스를 선택하는 조합을 구성하고, 각 조합에 따라 BFS로 바이러스가 퍼지는 시뮬레이션을 실시한다. BFS에서는 미리 체크한 빈칸의 갯수(벽과 바이러스를 제외한)를 확인하면서 빈칸이 0이 되었을 때 리턴한다. 소스 코드 및 결과 : pac.. 2021. 12. 27.

티스토리툴바