(Java) BFS & PriorityQueue (feat. 백준 16236 아기상어)
BFS (너비 우선 탐색)
BFS는 위의 그림과 같이 점차 탐색 영역을 확장시켜 나가는 알고리즘이다.
BFS는 그래프 탐색 문제에 적합한 알고리즘인데 이번에 풀어본 아기상어가 그래프 탐색 문제이다.
BFS의 원리는 간단하다.
1. Queue 자료구조에 그래프에서 현재 위치를 넣어준다.
2. 방문했던 곳을 다시 가지 않도록 방문처리를 해준다.
3. Queue에서 하나씩 Poll한다.
4. Poll한 위치에서 이동할 수 있는 그래프의 위치들을 탐색하고 이를 또 Queue에 Add한다.
5-1. 탐색 도중 조건에 맞는 위치가 나온다면 성공한 결과값과 함께 BFS 종료,
5-2. Queue에 더 이상 이동할 위치가 남아있지 않다면 실패 결과값과 함께 BFS 종료
기본 형태는 다음과 같다.
static boolean bfs(int start, int target, int[][] graph, boolean[] visited) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
while(!q.isEmpty()) {
int nodeIndex = q.poll();
if (nodeIndex == target) {
return true; // 목표 노드를 찾았으므로 true 반환
}
for(int i=0; i<graph[nodeIndex].length; i++) {
int temp = graph[nodeIndex][i];
if(!visited[temp]) {
visited[temp] = true;
q.offer(temp);
}
}
}
return false; // 목표 노드를 찾지 못했으므로 false 반환
}
PriorityQueue (우선순위 큐)
우선순위 큐는 BFS와 묶음으로 잘 쓰이곤 하는데 사용하는 이유는 탐색하는 노드 중에서 순위가 있는 경우 델타(상하좌우 탐색하는 알고리즘)만으로는 순위를 구현하기 어려운 경우가 있기 때문이다.
이번에 풀어본 아기상어 역시 그러한 예시이다.
또, 나중에 다뤄보겠지만 다익스트라 알고리즘 역시 노드들의 순위를 구현하기 위해 BFS와 우선순위 큐를 활용한다.
그만큼 BFS와 우선순위 큐는 자주 쓰이는 조합이고, 배워두면 좋다.
기본형태는 다음과 같다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
우선순위 큐는 내부의 구현된 인터페이스 Comparable이 있어 기본적으로 오름차순 정렬이 되어있다.
하지만 보통 우선순위 큐를 사용할 때는 우선순위를 조작해줘야 하는 경우가 대부분이다.
그래서 아래와 같이 우선순위 큐의 Comparator 인터페이스를 구현하여 우선순위를 조작해준다.
PriorityQueue<Student> PriorityQueue = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student p1, Student p2) {
return Integer.compare(p1.age, p2.age);
}
});
자바 8부터 적용된 람다식을 적용한다면 다음과 같다.
PriorityQueue<Student> PriorityQueue = new PriorityQueue<>(
(p1, p2) -> Integer.compare(p1.age, p2.age);
);
람다식에 대해 간단하게 설명하자면 인터페이스의 메소드가 하나라면 해당 메소드를 이름 생략하고 사용할 수 있는 편리한 기능이다. 람다식에 대해서도 나중에 다뤄보도록 하겠다.
백준 16236 아기상어
https://www.acmicpc.net/problem/16236
아기 상어의 위치와 물고기들이 위치한 N*N 크기의 공간 정보가 주어지고 아기 상어가 먹을 수 있는만큼 먹으면 시간이 얼마나 걸리는가에 대한 문제이다.
조건은 다음과 같다.
1. 자신보다 큰 물고기가 위치한 곳은 지나다닐 수 없다.
2. 자신보다 작은 물고기만 먹을 수 있다. 즉, 같은 크기의 물고기는 먹지 못하고 지나다닐 수만 있다.
3. 먹을 수 있는 물고기가 많다면, 거리가 가까운 물고기를 먹으러 간다.
4. 거리가 같은 경우 우선순위는 위쪽, 왼쪽이 된다.
5. 한칸 이동하는 시간은 1초이며, 이동 시간만 따지면 된다.
6. 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
풀이는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
static class Shark {
int r, c, dist;
Shark(int r, int c, int dist) {
this.r = r;
this.c = c;
this.dist = dist;
}
}
static int N, NArr[][], size, stack, time, locR, locC;
static int delR[] = {-1,0,0,1};
static int delC[] = {0,-1,1,0};
static boolean flag[][];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
NArr = new int[N+1][N+1];
size = 2;
stack = 0;
time = 0;
locR = 0; locC = 0;
for(int r = 1; r <= N; r++) {
st = new StringTokenizer(br.readLine());
for(int c = 1; c <= N; c++) {
NArr[r][c] = Integer.parseInt(st.nextToken());
if(NArr[r][c] == 9) {
locR = r;
locC = c;
NArr[r][c] = 0;
}
}
}
while(bfs(locR, locC)) {}
System.out.println(time);
}
static boolean bfs(int r, int c) {
PriorityQueue<Shark> pq = new PriorityQueue<>(
(s1, s2) -> {
if(s1.dist != s2.dist) {
return Integer.compare(s1.dist, s2.dist);
}
if(s1.r != s2.r) {
return Integer.compare(s1.r, s2.r);
}
return Integer.compare(s1.c, s2.c);
}
);
pq.add(new Shark(r, c, 0));
flag = new boolean[N+1][N+1];
flag[r][c] = true;
while(!pq.isEmpty()) {
Shark shark = pq.poll();
if(NArr[shark.r][shark.c] < size && NArr[shark.r][shark.c] != 0) {
NArr[shark.r][shark.c] = 0;
time += shark.dist;
stack++;
locR = shark.r;
locC = shark.c;
if(stack == size) {
size++;
stack = 0;
}
return true;
}
for(int d = 0; d < 4; d++) {
int dr = delR[d] + shark.r;
int dc = delC[d] + shark.c;
int dist = shark.dist + 1;
if(dr <= N && dc <= N && dr > 0 && dc > 0 && !flag[dr][dc] && NArr[dr][dc] <= size) {
flag[dr][dc] = true;
pq.add(new Shark(dr, dc, dist));
}
}
}
return false;
}
}
풀이 설명
1. 우선순위 큐에 넣을 Shark라는 객체를 만들어 위치와 이동한 거리를 저장할 수 있게 했다. 인스턴스 변수들을 통해 객체들의 우선순위를 정하고자 했다.
2. BFS를 한번 거치면 이동을 한번 한 것이 되는데 이러한 '현재 위치'를 저장할 변수가 필요했다. 이를 locR, locC에 저장했다.
3. 그래프의 상하좌우 이동을 위한 델타
4. BFS에서 방문처리를 하기 위한 flag 배열
5. 우선순위 큐에서 거리, 북쪽, 서쪽 순으로 우선순위를 조작한다.
6. 문제 조건에 맞게 BFS를 진행한다.
버그 디버깅
1. 북쪽, 서쪽 우선하는 조건을 델타로 충분할 줄 알고 풀었다. 하지만 큐에 넣는 순서에 따른 예외가 있었다. 그래서 우선순위 큐를 쓰게 되었다.
2. BFS 탈출 조건을 적어놓는 위치가 문제였다. 기존에는 델타를 실행하며(반복문 내부) if문으로 탈출 조건을 찾고 있었는데 이 경우 우선순위를 벗어나는 이슈가 있었다. 그래서 pq(우선순위 큐)에서 poll하자마자 탈출 조건을 찾는 것으로 변경했다.
3. 그래프에서 상어의 위치를 나타내는 9가 문제였다. 상어가 이동하면 9는 사실상 0인데 이를 처리해주지 않아 계속해서 9로 남아있었다. 이 부분을 0으로 고쳐줬다.
4. pq에서 거리 조건을 넣지 않았다. 1번에서 Queue에 먼저 들어가면 거리는 따져지겠지 착각했던 부분을 옮길 때에도 별도로 넣지 않았다. 거리 조건을 추가해줬다.