[백준/BFS] 16236: 아기상어 - 자바

문제

---

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

16236번: 아기 상어

 

풀이

---

시간초과가 나지 않을까? 처음에 효율적인 접근 방법이 있을까? 생각했다.

 

그런데 그냥 다음 로직처럼 구성하면 끝이였다.

1. 상어 위치를 경로 큐에 넣는다. (스타트)
2. 스타트에서 BFS 맵 전체를 탐색을 한다.
3. BFS 탐색하면서 자신이 먹을 수 있는 물고기의 위치와 떨어진 거리를 다른 물고기 리스트에 저장한다
4. 모든 맵의 거리와 물고기 위치를 탐색했으면 물고기 리스트를 순회한다
5. 물고기 리스트를 순회하면서 가장 거리가 작은 물고기를 임시 변수에 저장해둔다
   1. 리스트를 계속 순회하면서 거리가 더 작은 물고기가 있을시 임시 물고기 변수와 교체한다.
   2. 거리가 같다면 어느 물고기가 왼쪽에 있는지 검사한다.
   3. 두 물고기의 열이 같다면 행을 비교하여 어느 것이 더 위에 있는지 검사한다.
6. 4번과정 (a,b,c 조건을 통해) 을 만족한 물고기를 잡아먹고 해당 위치를 0으로 초기화한다.
7. 물고기를 잡아먹은 위치를 경로 큐에 넣고 3번 과정을 반복한다.
8. 더 이상 잡아먹을 물고기가 없으면 걸린시간을 출력하고 종료한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
/*
 * 메모리: 24252 KB
 * 시간: 204 ms
 * 코드길이: 2627 B
 */

public class BOJ_16236 {
	static int N;
	static int[][] map;
	// 4면 탐색
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int time = 0; // 이동시간
	static int sharkSize = 2; // 상어 크기
	static int sharkEatCnt = 0; // 상어 먹은 횟수 카운트
	static Queue<int[]> queue = new ArrayDeque<>(); // 이동경로 큐 생성

	public static void main(String[] args) throws NumberFormatException, IOException {
		input(); // 입력
		while (true) BFS(); // 아기상어가 계속 먹을 때까지 반복
	}

	public static void BFS() {
		List<int[]> fishList = new LinkedList<>(); // 먹을 수 있는 물고기 리스트 생성
		int[][] visited = new int[N][N]; // 방문체크와 거리 정보 저장을 위한 배열
		
		while (!queue.isEmpty()) {
			int[] q = queue.poll();

			int qx = q[0]; // x좌표
			int qy = q[1]; // y좌표

			for (int d = 0; d < 4; d++) { //4방면 탐색
				int nx = qx + dx[d];
				int ny = qy + dy[d];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && visited[nx][ny] == 0) { // 인덱 스 내에 방문하지 않은 곳 탐색
					// 상어는 자기 사이즈 보다 큰 물고기는 지나가지 못함
                    if (map[nx][ny] <= sharkSize) { 
						visited[nx][ny] = visited[qx][qy] + 1; // 상어의 거리로부터 거리 탐색하여 visited 배열에 저장
						queue.add(new int[] { nx, ny, visited[nx][ny] }); // 큐에 다음 탐색할 경로 넣기
                        
                        // 먹을 수 있는 물고기를 발견했다면 
						if (map[nx][ny] >= 1 && map[nx][ny] <= 6 && map[nx][ny] < sharkSize) { 
                        // 물고기 리스트에 좌표와 해당 지점으로 부터 떨어진 거리 큐에 넣기
							fishList.add(new int[] { nx, ny, visited[nx][ny] }); 
						}
					}
				}

			}
		}
		
		chooseFish(fishList); // 물고기 고르기
	}
	
	public static void chooseFish(List<int[]>  fishList) {
		if (fishList.size() == 0) { // 더이상 먹을 물고기가 없으면 총 걸린시간 출력 후 종료
			System.out.println(time);
			System.exit(0);
		}

		int[] currentFish = fishList.get(0); // 물고기 리스트에 맨 처음 인덱스 꺼내기
		for (int i = 1; i < fishList.size(); i++) { // 두번째 인덱스부터 거리가 가장 가까운 물고기 찾기
			if (fishList.get(i)[2] < currentFish[2]) {
				currentFish = fishList.get(i);
			}
			else if (fishList.get(i)[2] == currentFish[2]) { // 현재 물고기와 탐색한 물고기의 거리가 똑같다면
				if (currentFish[0] > fishList.get(i)[0]) { // 왼쪽에 있는 물고기인지 검사
					currentFish = fishList.get(i);
				} else if (currentFish[0] == fishList.get(i)[0]) { // 물고기 두개의 열이 같다면 행을 비교함 (맨 위에 있는 것 우선)
					if (currentFish[1] > fishList.get(i)[1])
						currentFish = fishList.get(i);
				}
			}
		}
		time += currentFish[2]; // 가장 가까운 거리의 물고기 거리를 time에 넣기
		sharkEatCnt++; // 한번 물고기를 먹었으니 카운트 증가
		map[currentFish[0]][currentFish[1]] = 0; // 물고기를 먹은 위치를 0으로 바꾸기
		if (sharkEatCnt == sharkSize) { // 상어가 자기 크기만큼 물고기를 먹었다면 
			sharkSize++; // 사이즈 업 & 횟수 초기화
			sharkEatCnt = 0;
		}

		// 물고기를 먹었으면 그 자리로부터 다시 먹을 수 있는 물고기를 탐색하기 위해 큐에 먹은 물고기 위치와 초기화된 거리(0) 을 넣기
		queue.add(new int[] { currentFish[0], currentFish[1], 0 }); 
	}

	public static void input() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) {
					queue.add(new int[] { i, j, 0 });
					map[i][j] = 0;
				}
			}
		}
	}
}