BFS11 [백준 Gold 5] 2589 보물섬 - Java 문제링크 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근 과정 : 임의의 육지 2개를 고르고, 그 사이의 최단거리가 가장 긴 거리를 탐색하는 문제이다. 육지 하나하나 모두 BFS 해서 최장 거리를 탐색하는 완전탐색 방법으로 풀이할 수 있다. ++ 한 번 거리가 측정된 경로는 다시 탐색하지 않고 사용하는 것이 시간을 줄일 수 있는 포인트.. 이 부분에 대해서는 좀 더 고민이 필요하다. 소스 코드 및 결과 : package BOJ; /* 보물.. 2021. 12. 29. [백준 Gold 4] 1261 알고스팟 - Java 문제링크 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 접근 과정 : 결국 목적지까지, 벽을 최소한으로 뚫고 가야하는 문제이다. 일반적으로 벽을 뚫은 횟수를 포함한 BFS를 생각했다. 우선순위큐로 벽을 뚫은 횟수가 가장 적은 경우를 꺼내면서 BFS 탐색을 실시했다. 벽을 만났을 때는, 벽을 뚫은 횟수+1 해서 우선순위 큐에 집어넣고, 벽이 아니면 현재 벽을 뚫은 횟수를 집어넣는다. 이렇게 하면 쉽게 해결할 수 있다. .. 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] 1525 퍼즐 - Java 문제링크 : https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 접근 과정 : 3x3 표를 하나의 문자열로 이어서 String으로 관리 0의 위치에 따라서, 이동이 가능한 다음 String을 BFS로 탐색하고, "123456780"과 같으면 종료. 방문체크는 HashSet으로 처리. 소스 코드 및 결과 : package BOJ; /* 퍼즐 */ import java.io.*; import java.util.*; public class BOJ1525 { static int[] dx = { -1, 1, 0, 0 }; static.. 2021. 12. 19. 이전 1 2 3 다음
