BFS

[JAVA] 백준 2636 : 치즈

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 해결 방법 조금 생각할 것이 있는 구현 문제이다. 필자는 다음과 같은 순서로 문제를 해결했는데, 1. 배열의 (0, 0) 부터 빈 공간인 0을 탐색, 만약 0의 상하좌우에 치즈 즉, 1이 있다면 Queue에 넣음. 모든 공간을 다 탐색하면 Queue에 넣어진 치즈들이 한 시간 후 녹을 치즈들이 됨. 재귀를 통해서 모든 치즈들이 없어질 때까지 탐색을 계속함. 2. Queue에서 치즈를 꺼내면서 빈공간으로 바꿔주면서 상하좌우에 있는 치즈를 찾음. 만약 치즈가 있다면 다..

[JAVA] 백준 13913 : 숨바꼭질 4

문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결 방법 오랜만에 알고리즘 해설을 준비했는데, 그리 어렵지 않은 문제이다. 어려운 문제는 어떻게 풀어야 할지 아직 감이 잘 안 잡혀서, 문제를 풀더라도 설명을 할 정도로 이해를 하지 못해 가져오지 못했다. 이 문제는 수빈이가 동생을 찾는 숨바꼭질 문제인데, 수빈이는 현재 위치에서 +1, -1 또는 x2 만큼 움직일 수 있고 움직일 때마다 1초씩 소모된다. 즉, 모든 경우의 수를 전부 확인하며 목표지점에 도달하는 시간을 체크..

[JAVA] 백준 2151 : 거울 설치

문제 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 해결 방법 빛은 일직선으로 나아가고, 45도 각도의 거울을 사용해서 이동방향을 바꿔 목적지에 도착하도록 하는 문제이다. 그래서 현재 방향이 어디인지 저장할 dir을 사용하고, cnt를 사용해서 거울을 몇 번 사용했는지 체크하게끔 class를 구성했다.또 우선순위 큐를 사용해서 가장 거울을 적게 사용한 결괏값이 제일 먼저 목적지에 도착하도록 하였다. 시작점과 도착점이 문제와 같이 2개만 주어지는 문제는 처음 입력을 받을 때 해당 지점을 체크해두고..

[JAVA] 백준 1240 : 노드사이의 거리

문제 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해결 방법 가중치가 있는 트리의 탐색 문제의 기본이다. class를 이용해서 다음 방문할 위치와 거리를 입력해두고 탐색하면서 거리를 계속 더 해주면 된다. 탐색은 BFS를 사용했다. 간선을 입력할 때 양쪽으로 이동이 가능하게끔 쌍방향으로 리스트에 넣어주어야 한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java..

[JAVA] 백준 11967 : 불켜기

문제 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 해결 방법 루모스 ~ 기본적인 탐색 문제에서 불을 켜고, 불이 켜진 방만 이동이 가능한 조금 응용된 문제이다. 각 방에 있는 스위치를 나타내기 위해서 ArrayList 배열을 사용해서 리스트에 불을 켤 수 있는 곳의 좌표를 넣어 두었고, light와 visit을 활용해서 불이 켜져 있는지 여부와 방문 여부를 체크하였다. 탐색은 BFS를 사용했는데 불을 켤 수 있는 방이 존재하는지 여부는 리스트가 비었는지 ..