너비우선탐색9 [백준 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. [백준 Gold 4] 3055 탈출 - Java 문제링크 : https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 접근 과정 : 일반적인 BFS 방식으로 접근 물이 찰 공간으로 고슴도치가 이동할 수 없다. 시간++ -> 물 이동 -> 고슴도치 이동 순으로 반복해서 가장 빠른 시간을 탐색 만약 고슴도치가 더 이상 이동할 수 없다면, 비버의 집에 갈 수 없다!! 소스 코드 및 결과 : package BOJ; /* 탈출 */ import java.io.*; import java.util.*; public class.. 2021. 12. 18. [백준 Gold 4] 1600 말이 되고픈 원숭이 - Java 문제링크 : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 접근 과정 : BFS 방식으로 접근해야겠다고 생각 BFS를 진행하면서, 방문체크를 어떻게 해야할 지 고민 int[][] visit로 방문을 체크하되. 그 값을 방문 당시의 남아있는 점프횟수로 하였다. 즉, visit[i][j]의 값의 현재 k의 값보다 크다면, 이미 이전에 방문했던 적이 있다고 판단. 소스 코드 및 결과 : package BOJ; /* 말이 되고픈 원숭.. 2021. 12. 18. 이전 1 2 3 다음
