백준 알고리즘 - 16236_아기 상어

https://www.acmicpc.net/problem/16236

문제 설명

N × N 크기의 공간에 M 마리의 물고기가 있다.
처음 아기상어의 크기는 2 이고, 아기상어는 자신보다 작은 크기의 물고기만 먹을 수 있다.
먹은 물고기의 수가 아기상어의 크기와 같아지면, 크기는 한 단계 증가한다.
다음은 아기상어가 먹을 물고기를 탐색하는 조건이다.

• 먹을 수 있는 물고기가 여러 마리일 경우
  아기상어와 가장 가까운 물고기를 잡아먹는다.
  
  

• 아기상어와 가장 가까운 물고기가 여러마리일 경우
  1) 가장 위에 있는 물고기
  2) 가장 왼쪽에 있는 물고기
  순으로 우선순위에 만족하는 물고기를 먹는다.
  
  

• 아기상어는 상하좌우로 이동할 수 있으며, 자신보다 큰 물고기가 있는 공간은 지나갈 수 없다

• 공간에 물고기가 없을 경우
  엄마 상어를 부른다.

아기상어의 이동시간은 1초이고, 물고기를 먹는데 걸리는 시간은 없다.

공간이 주어졌을 때, 아기상어는 몇 초동안 엄마상어를 부르지 않고 물고기를 먹을 수 있는지 구하는 것이 이 문제의 요구사항이다.

문제 풀이

이 문제를 푸느라 처음에 엄청나게 고생했다.
문제에서 주어진 테스트케이스 3번까지 정답이 나오는데, 그 외 테스트케이스에서는 오답이 나오고 있었다.

잘못 풀이한 코드

package backJoon_16236_BabyShark;
import java.util.*;
/*
 * 
 * 백준알고리즘
 * 16236. 아기상어
 * https://www.acmicpc.net/problem/16236
 * 2021-04-08
 * 
 * */
public class Practice {
	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[][] map;
	static Queue<Coordinate> q = new LinkedList<>();
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, -1, 0, 1};
	static int levelOfBabyShark = 2;
	static boolean[][] visited = new boolean[N][N];
	static Coordinate coordOfBabyShark;
	
	public static class Coordinate{
		int y;
		int x;
		int sec;
		
		public Coordinate(int y, int x, int sec) {
			this.y = y;
			this.x = x;
			this.sec = sec;
		}
	}
	
	public static void main(String[] args) {
		readInput();
		System.out.println(searchFish());
	}

	private static int searchFish() {
		//최초 아기상어 위치를 중심으로 가장 가까운 물고기 탐색
		q.offer(coordOfBabyShark);
		
		int second = 0;
		int gaugeOfLevelUp = 0;
		
		while(!q.isEmpty()) {
			Coordinate coord = q.poll();
			second = coord.sec;
			
			//상좌하우 순으로 가장 가까운 물고기 탐색
			int ny, nx;
			for(int d = 0; d < 4; d++) {
				ny = dy[d] + coord.y;
				nx = dx[d] + coord.x;
				
				//물고기 찾을때까지 탐색, 아기상어보다 같거나 작아야만 지나갈 수 있음
				if(isArrange(ny, nx) && visited[ny][nx] == false && map[ny][nx] != 9 && map[ny][nx] <= levelOfBabyShark) {
					//q에넣음
					q.offer(new Coordinate(ny, nx, second + 1));
					visited[ny][nx] = true;
					
					//물고기가 먹이라면
					if(map[ny][nx] < levelOfBabyShark) {
						map[ny][nx] = 0;
						gaugeOfLevelUp++;
						//visited 초기화
						for(int i = 0; i < N; i++) {
							for(int j = 0; j < N; j++) {
								visited[i][j] = false;
							}
						}
						
						//아기상어 레벨업 유무
						if(levelOfBabyShark == gaugeOfLevelUp) {
							levelOfBabyShark++;
							gaugeOfLevelUp = 0;
						}
					}
					
				}
			}
		}
		
		return levelOfBabyShark;
	}

	private static boolean isArrange(int ny, int nx) {
		return ny >= 0 && nx >= 0 && ny < N && nx < N;
	}

	private static void readInput() {
		N = sc.nextInt();
		map = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) {//아기상어의 최초 위치를 q에 넣음
					coordOfBabyShark = new Coordinate(i, j, 0);
				}
			}
		}
		
		//testInput
		/*
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}*/
	}
	
}

처음엔 어디가 틀렸는지 조차 잡아내지 못했다.
알고보니 두 번째 조건을 잘못 이해하고 있었다.

static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};

가장 위, 가장 왼쪽에 있는 물고기부터 탐색하라는 줄 알고 상좌하우 순으로 dy dx 값을 주기만 하면 될 줄 알았는데 어림도 없는 소리였다. ㅋㅋ

그러면 도대체 가장 위, 가장 왼쪽에 있는 물고기부터 먹으란게 무슨 소리인지 이해할 수 없었다.

당연히 탐색을 위, 왼쪽 순으로 하면 자연스레 가장 위, 왼쪽에 있는 파란색 물고기부터 먹어질 것 아닌가?
하지만 아니었다.

아래의 그림을 보자.

그림의 숫자는 물고기의 크기를 뜻한다.
그림과 같은 상태의 공간이 주어진다면, 맨 처음 탐색되는 물고기는 어느 색 물고기일까?

당연히 정답은 노란색 물고기일 것이다.
그런데 상좌하우 순으로만 탐색하게 하면 노란색이 아닌 보라색 물고기부터 잡아먹게 된다..
왜 그럴까?

맨 처음 상좌하우 순대로, 가장 위부터 탐색하게 되므로 빨간색 물고기가 있는 공간으로 이동해야 되지만, 아기상어보다 크므로 지나갈 수 없다.

따라서 아기상어의 위쪽 말고 왼쪽 좌표가 먼저 q에 담겨지게 되면서 보라색 물고기가 먼저 탐색되는 것이다.


이 문제를 해결하기 위해서는 우선, 탐색하며 맨 처음 찾아지는대로 물고기 좌표를 바로 q에 넣으면 안된다는 것이다.
그랬다간 위에 설명한 예시대로 노란색 물고기가 아닌 보라색 물고기부터 찾아질 것이다.

때문에 물고기를 탐색하며, 사냥가능한 물고기를 feedList 에 따로 저장하는 식으로 풀어야 한다.

전체 코드

package backJoon_16236_BabyShark;
import java.util.*;


public class Practice5 {
	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[][] map;
	static boolean[][] visited;
	static Fish babyShark;
	static List<Fish> feedList = new ArrayList<>(); //아기상어가 먹을 물고기 목록
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, -1, 0, 1};
	static int sizeOfBabyShark = 2;
	static int guageForSizeUp = 0;
	static int allTime = 0;
	
	public static class Fish{
		int y;
		int x;
		int time;
		
		public Fish(int y, int x, int time) {
			this.y = y;
			this.x = x;
			this.time = time;
		}
	}
	
	public static void main(String[] args) {
		readInput();
		simulation();
		System.out.println(allTime);
	}

	private static void simulation() {
		Queue<Fish> q = new LinkedList<>();
		q.add(babyShark);
		visited[babyShark.y][babyShark.x] = true;
		
		while(true) { //가장 가까운 먹이를 찾으면 다음 먹이를 찾게 하기 위한 while문
			while(!q.isEmpty()) { //BFS) 가장가까운 먹이를 찾게 하기 위한 while문
				Fish fish = q.poll();
				int time = fish.time;
				
				for(int d = 0; d < 4; d++) {
					int ny = fish.y + dy[d];
					int nx = fish.x + dx[d];
					
					if(!isArrange(ny, nx) || visited[ny][nx]) continue; //범위 밖이면 다음 d
					
					//식사 가능 -> 먹이리스트 추가
					if(map[ny][nx] < sizeOfBabyShark && map[ny][nx] != 0) {
						q.add(new Fish(ny, nx, time + 1));
						visited[ny][nx] = true;
						feedList.add(new Fish(ny, nx, time + 1));
						
					//이동만 가능 -> q에 추가	
					}else if(map[ny][nx] == 0 || map[ny][nx] == sizeOfBabyShark) {
						q.add(new Fish(ny, nx, time + 1));
						visited[ny][nx] = true;
					}
				}
			} // while(!q.isEmpty()) 종료
			
			//탐색 종료 후, 먹이리스트 확인
			if(feedList.size() > 0) {
				eat(); //식사
				
				//식사 후, 방문 배열 초기화
				initVisited();
				
				//q 초기화 후 다시 아기상어의 위치를 세팅
				q.clear();
				q.add(babyShark);
				visited[babyShark.y][babyShark.x] = true;
			}else {
				return; //while(true) 무한반복문이 있기 때문에 반드시 return을 선언해줘야함
			}
		} // while(true) 종료
	}


	private static void initVisited() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				visited[i][j] = false;
			}
		}
	}

	private static void eat() {
		//feedList를 오름차순으로 정렬하여 그중 맨 첫번째꺼 먹는다
		Collections.sort(feedList, new Comparator<Fish>() {
			@Override
			public int compare(Fish o1, Fish o2) {
				return o1.time != o2.time ? Integer.compare(o1.time, o2.time) 
						: (o1.y != o2.y ? Integer.compare(o1.y, o2.y) 
								: (o1.x != o2.x ? Integer.compare(o1.x, o2.x) : Integer.compare(o1.y, o2.y)));
			}
		});
		
		//위, 왼쪽기준 가장 가까운 물고기 먹는다
		Fish fish = feedList.get(0);
		allTime += fish.time;
		map[fish.y][fish.x] = 0; //먹힌 물고기 자리는 0으로 변경
		
		//아기상어의 위치를 먹은 물고기 위치로 변경
		babyShark.y = fish.y;
		babyShark.x = fish.x;
		
		//게이지가 다 찼으면 사이즈 +1
		if(++guageForSizeUp == sizeOfBabyShark) {
			++sizeOfBabyShark;
			guageForSizeUp = 0; //후에 다시 게이지를 비움
		}
		
		feedList.clear(); //바뀐 위치에서의 새 물고기 탐색을 위해 먹이리스트 초기화
	}

	
	private static boolean isArrange(int ny, int nx) {
		return ny >= 0 && nx >= 0 && ny < N && nx < N;
	}

	private static void readInput() {
		N = sc.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) {
					babyShark = new Fish(i, j, 0); //아기상어 최초위치
					map[i][j] = 0;
				}
			}
		}
	}

}

문제 풀이

• 아기 상어의 위치를 중심으로, 전체를 탐색하며 사냥 가능한 물고기를 feedList에 넣는다.

while(!q.isEmpty()) { //BFS) 가장가까운 먹이를 찾게 하기 위한 while문
	Fish fish = q.poll();
	int time = fish.time;
				
	for(int d = 0; d < 4; d++) {
		int ny = fish.y + dy[d];
		int nx = fish.x + dx[d];
					
		if(!isArrange(ny, nx) || visited[ny][nx]) continue; //범위 밖이면 다음 d
					
		//식사 가능 -> 먹이리스트 추가
		if(map[ny][nx] < sizeOfBabyShark && map[ny][nx] != 0) {
			q.add(new Fish(ny, nx, time + 1));
			visited[ny][nx] = true;
			feedList.add(new Fish(ny, nx, time + 1));
						
		//이동만 가능 -> q에 추가	
		}else if(map[ny][nx] == 0 || map[ny][nx] == sizeOfBabyShark) {
			q.add(new Fish(ny, nx, time + 1));
			visited[ny][nx] = true;
		}
	}
} // while(!q.isEmpty()) 종료

• 전체 탐색이 끝났으면 feedList 를 아기상어와의 거리 가장 위쪽 가장 왼쪽 순으로 정렬해, 그 중 첫번째 물고기를 먹는다.

private static void eat() {
	//feedList를 오름차순으로 정렬하여 그중 맨 첫번째꺼 먹는다
	Collections.sort(feedList, new Comparator<Fish>() {
		@Override
		public int compare(Fish o1, Fish o2) {
			return o1.time != o2.time ? Integer.compare(o1.time, o2.time) 
			    : (o1.y != o2.y ? Integer.compare(o1.y, o2.y) 
			    : (o1.x != o2.x ? Integer.compare(o1.x, o2.x) : Integer.compare(o1.y, o2.y)));
		}
	});
		
	//위, 왼쪽기준 가장 가까운 물고기 먹는다
	Fish fish = feedList.get(0);
	allTime += fish.time;
	map[fish.y][fish.x] = 0; //먹힌 물고기 자리는 0으로 변경
		
	//아기상어의 위치를 먹은 물고기 위치로 변경
	babyShark.y = fish.y;
	babyShark.x = fish.x;
		
	//게이지가 다 찼으면 사이즈 +1
	if(++guageForSizeUp == sizeOfBabyShark) {
		++sizeOfBabyShark;
		guageForSizeUp = 0; //후에 다시 게이지를 비움
	}
		
	feedList.clear(); //바뀐 위치에서의 새 물고기 탐색을 위해 먹이리스트 초기화
}

• while(true) 에 의해 물고기를 잡아먹은 위치에서 다시 탐색을 시작한다.

//탐색 종료 후, 먹이리스트 확인
if(feedList.size() > 0) {
	eat(); //식사
				
	//식사 후, 방문 배열 초기화
	initVisited();
				
	//q 초기화 후 다시 아기상어의 위치를 세팅
	q.clear();
	q.add(babyShark);
	visited[babyShark.y][babyShark.x] = true;
}else {
	return; //while(true) 무한반복문이 있기 때문에 반드시 return을 선언해줘야함
}

• 위의 과정을 반복하며 모든 물고기를 잡아 먹었을 경우, return 에 의해 while(true) 문을 빠져나가며 종료된다.

Git gist 주소

https://gist.github.com/ysyS2ysy/aa5f0a4220d8e1b67b13d55ca5de501e