BOJ_16236_아기 상어_JAVA
문제 : 아기 상어
링크 : BOJ_16236_아기상어
접근 방식
혼자 풀었던 방식의 개요는 아래와 같다.
한 번 이동시마다 1초씩 증가
배열을 탐색하며 상어의 크기보다 작은 물고기들을(먹을 수 있는 물고기) 리스트에 넣는다 집어넣는 값은 좌표.
거리가 같다면 높이가 높은 쪽, 높이도 같다면 가장 왼쪽부터 먹는다.
상어는 몸 크기가 2로 시작하며, 자신보다 크기가 큰 물고기는 지나가지 못한다 (벽 취급)
리스트에서 하나씩 꺼내며 거리가 가장 짧은 좌표를 구한다. ( 이 때 먹을 수 있는지 없는지도 판단해야겠다. 만약 작은물고기가 있을 지라도 경로상 도달하지 못하면 못먹는 물고기이다.)
해당 위치로 이동하고 거리만큼 시간을 더해준다.
BFS 탐색을 통하면 현재 상어의 위치부터 물고기까지의 최단거리를 구할 수 있다.
한 번 물고기를 먹은 후 리스트를 초기화하고, 다시 배열을 탐색하며 물고기의 좌표를 리스트에 저장한다.
위의 방식으로 정답을 맞추긴 했으나, 다른 풀이에 비해서 시간은 4~5배, 메모리는 8~9배 정도로 자원사용량이 너무 컸다. 한 번 이동할 때마다 리스트 새로 생성하고, 배열을 다시 탐색하면서 리스트에 값 집어넣고 하는 과정들이 시간과 메모리 소모가 너무 컸던 것으로 예상된다.
이러한 문제의 해결 방법으로 우선순위 큐라는 것을 알게 되었다. 또한 로직도 배열 기준이 아닌 상어를 중심으로 움직이도록 일부 수정했다.
이전처럼 배열을 탐색하며 물고기 위치를 저장해두는 것이 아니라, 상어의 위치만 기억해두고 BFS를 수행한다. BFS에서, 상어는 1번 움직일때마다 자신이 가지고 있는 dist값을 1씩 증가시키면서 이동한다.
BFS 탐색 도중 만나는 물고기에 대해 먹을 수 있는 물고기인지 확인 후, 먹을 수 있는 물고이라면 상어의 dist값을 부여하고 생성하여 우선순위 큐에 추가한다.
우선순위큐(오름차순)는 큐에 들어있는 값을 자동으로 오름차순으로 꺼내준다. 큐의 우선순위를 정하는 부분을 아래 문구에 맞게 CompareTo 메서드를 재정의 한다.
“거리가 같다면 높이가 높은 쪽, 높이도 같다면 가장 왼쪽부터 먹는다.”
이렇게 우선순위 큐에 먹을 수 있는 생선을 집어넣고, 가장 먼저 poll한 값이 현재 상어의 위치에서 가장 가까운 물고이의 위치이다.
이후 재귀호출을 하여 다음 먹이를 계속해서 찾아주고, BFS 탐색을 한 뒤에 우선순위큐에 어떠한 값도 들어가 있지 않다면(기저조건) 더이상 먹을 수 있는 물고기가 없다는 뜻이므로 return한다.
우선순위큐를 사용하자 코드가 훨씬 간결해졌고, 로직변경과 더해져 수행속도, 메모리 사용량이 대폭 감소했다.
소스 코드 : 리스트 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
/*
거리
|x-x1| + |y-y2|
거리가 같다면 가장 왼쪽
한 번 이동시마다 1초씩 증가
배열을 탐색하며 상어의 크기보다 작은 물고기들을 리스트에 넣는다 집어넣는 값은 좌표
리스트에서 하나씩 꺼내며 거리가 가장 짧은 좌표를 구한다. ( 이 때 먹을 수 있는지 없는지도 판단해야겠다)
해당 위치로 이동하고 거리만큼 시간을 더해준다.
위 내용을 반복하려고 했지만 안되네 자기보다 큰 물고기는 못지나가기 때문에 거리를 계산하지 말고 움직여야할듯.... 이거 어케하지? -> 찾아보니까 BFS 탐색을 통하면 최단거리를 구할 수 있다. 벽부수고이동하기 참고.
*/
class Distance implements Comparable<Distance> {
int x;
int y;
int body;
int dist;
public Distance(int x, int y, int body) {
super();
this.x = x;
this.y = y;
this.body = body;
}
public Distance(int x, int y, int body, int dist) {
super();
this.x = x;
this.y = y;
this.body = body;
this.dist = dist;
}
@Override
public int compareTo(Distance o) {
// TODO Auto-generated method stub
return 0;
}
}
public class BOJ_16236_아기상어 {
static int N;
static int[][] arr;
static List<Distance> list;
static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
static int min;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
arr = new int[N + 1][N + 1];
list = new ArrayList<>();
StringTokenizer st;
Distance shark = null;
// 배열에 값 할당, 초기에 상어가 먹을 수 있는 값의 위치 저장하기.
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(in.readLine(), " ");
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1) {
list.add(new Distance(i, j, arr[i][j]));
}
if (arr[i][j] == 9) {
shark = new Distance(i, j, 2);
}
}
}
// 먹을 수 있는 먹이가 없을 때
if (list.size() == 0) {
System.out.println(0);
return;
}
int answer =0;
int cnt = 0;
while (true) {
Distance minfish = null;
min = Integer.MAX_VALUE;
for (int i = 0, n = list.size(); i < n; i++) {
Distance temp = bfs(shark, list.get(i), new boolean[N+1][N+1]);
if(temp.dist == 0) {
continue;
}
if(temp.dist < min) {
min = temp.dist;
minfish = temp;
}else if(temp.dist == min) {
if(temp.x < minfish.x) {
min = temp.dist;
minfish = temp;
}else if(temp.x == minfish.x) {
if(temp.y < minfish.y) {
min = temp.dist;
minfish = temp;
}
}
}
}
if(minfish == null) {
System.out.println(answer);
return;
}
cnt++;
answer += minfish.dist;
// System.out.println(answer);
// for(int i=0;i<N;i++) {
// System.out.println(Arrays.toString(arr[i]));
// }
arr[shark.x][shark.y] = 0;
arr[minfish.x][minfish.y] = 9;
shark.x = minfish.x;
shark.y = minfish.y;
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println("dist:"+minfish.dist);
System.out.println("answer: "+answer);
System.out.println("====================");
System.out.println();
if(cnt == shark.body) {
shark.body++;
cnt = 0;
}
list = new ArrayList<>();
for(int i =1 ;i<=N;i++) {
// System.out.println(Arrays.toString(arr[i]));
for(int j=1;j<=N;j++) {
if(arr[i][j] != 0 && arr[i][j] < shark.body) {
list.add(new Distance(i,j,arr[i][j]));
}
}
}
}
}
static Distance bfs(Distance shark, Distance fish, boolean[][] visited) {
Queue<Distance> queue = new LinkedList<Distance>();
int x;
int y;
queue.add(new Distance(shark.x,shark.y, shark.body));
visited[shark.x][shark.y] = true;
int sharkBody = shark.body;
while(!queue.isEmpty()) {
Distance point = queue.poll();
x = point.x;
y = point.y;
if(x == fish.x && y == fish.y) {
return point;
}
for(int d=0;d<4;d++) {
int dx = x + dir[d][0];
int dy = y + dir[d][1];
if(dx > 0&& dx<= N && dy > 0 && dy <= N) {
if(sharkBody >= arr[dx][dy] && !visited[dx][dy]) {
visited[dx][dy] = true;
queue.offer(new Distance(dx, dy, sharkBody,point.dist+1));
}
}
}
}
// 경로가 없는 경우
return new Distance(0,0,0);
}
}
소스 코드 : 우선순위 큐 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
/*
거리
|x-x1| + |y-y2|
거리가 같다면 가장 왼쪽
한 번 이동시마다 1초씩 증가
배열을 탐색하며 상어의 크기보다 작은 물고기들을 리스트에 넣는다 집어넣는 값은 좌표
리스트에서 하나씩 꺼내며 거리가 가장 짧은 좌표를 구한다. ( 이 때 먹을 수 있는지 없는지도 판단해야겠다)
해당 위치로 이동하고 거리만큼 시간을 더해준다.
위 내용을 반복하려고 했지만 안되네 자기보다 큰 물고기는 못지나가기 때문에 거리를 계산하지 말고 움직여야할듯.... 이거 어케하지? -> 찾아보니까 BFS 탐색을 통하면 최단거리를 구할 수 있다. 벽부수고이동하기 참고.
*/
class Distance implements Comparable<Distance> {
int x;
int y;
int body;
int dist;
public Distance(int x, int y, int body) {
super();
this.x = x;
this.y = y;
this.body = body;
}
public Distance(int x, int y, int body, int dist) {
super();
this.x = x;
this.y = y;
this.body = body;
this.dist = dist;
}
@Override
public int compareTo(Distance o) {
// TODO Auto-generated method stub
return 0;
}
}
public class BOJ_16236_아기상어 {
static int N;
static int[][] arr;
static List<Distance> list;
static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
static int min;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
arr = new int[N + 1][N + 1];
list = new ArrayList<>();
StringTokenizer st;
Distance shark = null;
// 배열에 값 할당, 초기에 상어가 먹을 수 있는 값의 위치 저장하기.
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(in.readLine(), " ");
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1) {
list.add(new Distance(i, j, arr[i][j]));
}
if (arr[i][j] == 9) {
shark = new Distance(i, j, 2);
}
}
}
// 먹을 수 있는 먹이가 없을 때
if (list.size() == 0) {
System.out.println(0);
return;
}
int answer =0;
int cnt = 0;
while (true) {
Distance minfish = null;
min = Integer.MAX_VALUE;
for (int i = 0, n = list.size(); i < n; i++) {
Distance temp = bfs(shark, list.get(i), new boolean[N+1][N+1]);
if(temp.dist == 0) {
continue;
}
if(temp.dist < min) {
min = temp.dist;
minfish = temp;
}else if(temp.dist == min) {
if(temp.x < minfish.x) {
min = temp.dist;
minfish = temp;
}else if(temp.x == minfish.x) {
if(temp.y < minfish.y) {
min = temp.dist;
minfish = temp;
}
}
}
}
if(minfish == null) {
System.out.println(answer);
return;
}
cnt++;
answer += minfish.dist;
// System.out.println(answer);
// for(int i=0;i<N;i++) {
// System.out.println(Arrays.toString(arr[i]));
// }
arr[shark.x][shark.y] = 0;
arr[minfish.x][minfish.y] = 9;
shark.x = minfish.x;
shark.y = minfish.y;
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println("dist:"+minfish.dist);
System.out.println("answer: "+answer);
System.out.println("====================");
System.out.println();
if(cnt == shark.body) {
shark.body++;
cnt = 0;
}
list = new ArrayList<>();
for(int i =1 ;i<=N;i++) {
// System.out.println(Arrays.toString(arr[i]));
for(int j=1;j<=N;j++) {
if(arr[i][j] != 0 && arr[i][j] < shark.body) {
list.add(new Distance(i,j,arr[i][j]));
}
}
}
}
}
static Distance bfs(Distance shark, Distance fish, boolean[][] visited) {
Queue<Distance> queue = new LinkedList<Distance>();
int x;
int y;
queue.add(new Distance(shark.x,shark.y, shark.body));
visited[shark.x][shark.y] = true;
int sharkBody = shark.body;
while(!queue.isEmpty()) {
Distance point = queue.poll();
x = point.x;
y = point.y;
if(x == fish.x && y == fish.y) {
return point;
}
for(int d=0;d<4;d++) {
int dx = x + dir[d][0];
int dy = y + dir[d][1];
if(dx > 0&& dx<= N && dy > 0 && dy <= N) {
if(sharkBody >= arr[dx][dy] && !visited[dx][dy]) {
visited[dx][dy] = true;
queue.offer(new Distance(dx, dy, sharkBody,point.dist+1));
}
}
}
}
// 경로가 없는 경우
return new Distance(0,0,0);
}
}