문제

BOJ 16236: 아기 상어 https://www.acmicpc.net/problem/16236

풀이

조건

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 상어가 물고기까지 이동하는 칸의 갯수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 상어의 초기 크기는 2이다.
• 상어는 1초에 상하좌우로 움직이고 물고기를 먹는 행위는 시간을 추가하지 않는다.
• 상어는 자신의 크기보다 큰 물고기의 위치로는 갈 수 없다.
• 상어는 자신의 크기만큼 물고기를 먹으면 크기가 +1이 된다.
• 상어의 크기와 물고기의 크기가 같다면 먹을 순 없지만 해당 위치로 이동은 할 수 있다.

풀이 순서

• 최단 경로를 구해야 하므로 BFS를 사용한다.
• 상어의 초기 위치(9)의 좌표를 따로 저장해놓고 해당 위치는 0으로 바꾼다.
  • 탐색 시에 해당 위치도 탐색해야 하기 때문이다.
• while문 안에 bfs를 시작한다.
  • while문이 돌 때 마다 dist[][], minX, minY, minDist 를 초기화한다.
  • 다음 bfs()에 들어갈 상어의 위치가 이전 위치 기준으로 최단 거리에 있는 물고기의 위치가 되기 때문이다.
  • dist[][]에는 좌표마다 최단 거리가 값으로 입력되는데, 여기서 0이 아닌 위치는 방문 처리가 된 것으로 간주할 수 있다.
• bfs() 를 호출한다.
  • bfs() 내부에서 새롭게 탐색한 위치가 범위 안 && 탐색할 수 있는 위치 && 아직 방문하지 않은 위치 인지 확인한다.
  • 위의 조건에 해당하면 dist[][] 의 해당 좌표에 이전 좌표값 + 1 을 해준다.
  • 새롭게 탐색한 위치에 물고기가 있고 그 물고기가 상어보다 크기가 작은지 확인한다.
  • 위의 조건에 해당한다면 해당 위치에 있는 물고기의 거리가 가장 가까운지, 거리가 같다면 가장 윗쪽인지, 가장 왼쪽인지 확인한다.
• bfs()가 끝나면 다음 bfs()로 들어가기 위한 준비를 한다.
  • 상어 사이즈와 상어가 물고기를 먹은 횟수를 갱신해주고 bfs()에 넣을 새로운 좌표를 갱신해준다.
• minX, minY가 초기화 한 값과 같다면 더 이상 먹을 수 있는 물고기가 없다는 뜻이므로 종료한다.

코드

import java.util.*;
import java.io.*;

public class Main {

	static int N;
	static int[][] map; // 입력 받은 원본 배열
	static int[][] dist; // 여러 물고기가 있을 때 거리 체크할 배열
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int size = 2; // 상어 사이즈
	static int eat = 0; // 상어가 물고기 먹은 횟수
	static int cnt = 0; // 상어가 이동한 횟수
	static int sharkX = -1; // 상어의 X 좌표
	static int sharkY = -1; // 상어의 Y 좌표
	static int minX, minY, minDist; // while문 탈출 조건으로 쓸 변수
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if(map[i][j] == 9) {
					sharkX = i;
					sharkY = j;
					map[i][j] = 0; // 상어가 있었던 위치도 이 후로 탐색해야 하므로 0으로 초기화
				}
			}
		}
		
		while(true) {
			dist = new int[N][N]; // 거리 알아낼 배열 && 자동으로 방문 처리 됨
			minX = Integer.MAX_VALUE; // 상어에서 가장 가까이 있는 물고기 X좌표
			minY = Integer.MAX_VALUE; // 상어에서 가장 가까이 있는 물고기 Y좌표
			minDist = Integer.MAX_VALUE; // 상어에서 가장 가까이 있는 물고기 거리
			
			bfs(sharkX, sharkY); // 가장 가까이 있는 먹을 수 있는 물고기 먹으러 가는 메소드
			
			// 먹을 수 있는 물고기의 위치로 이동했다면
			if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
				eat++; // 상어가 먹은 물고기 횟수
				map[minX][minY] = 0; // 물고기를 먹었으므로 해당 위치는 0으로 갱신
				sharkX = minX; // 먹은 물고기의 X좌표가 현재 상어의 X좌표
				sharkY = minY; // 먹은 물고기의 Y좌표가 현재 상어의 Y좌표
				cnt += dist[minX][minY]; // 상어가 이동한 횟수는 해당 dist배열의 값을 더한 값이다
				
				// 물고기를 먹은 횟수가 상어의 현재 사이즈와 같다면
				if(eat == size) {
					size++; // 상어의 사이즈 + 1
					eat = 0; // 물고기 먹은 횟수 0으로 갱신
				}
			} else { // minX, minY가 초기값과 같다면 더 이상 먹을 물고기가 없다는 뜻이다.
				break;
			}
		}
		
		System.out.println(cnt);
	}
	
	static void bfs(int x, int y) {
		Queue<Pos> que = new LinkedList<>(); // 메소드가 호출 될 때 마다 새로운 큐를 사용해야 하므로 여기에 큐 생성
		que.add(new Pos(x, y));
		
		while(!que.isEmpty()) {
			
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				// 새롭게 탐색한 위치가 범위 안 && 그 위치가 탐색할 수 있는 위치 && 아직 방문한 적 없는 위치 라면?
				if(isArea(nx, ny) && isAblePos(nx, ny) && dist[nx][ny] == 0) {
					// 거리 배열에 (이전 배열의 값 + 1)의 값을 넣어주어 최소 거리를 입력함
					dist[nx][ny] = dist[curX][curY] + 1;
					
					// 해당 위치에 물고기가 있고 그 물고기가 상어보다 크기가 작다면?
					if(isEat(nx, ny)) {
						// 탐색한 위치에 있는 물고기의 거리가 가장 가까운 지 알아봄
						if(minDist > dist[nx][ny]) { // 더 가까운 물고기라면?
							minDist = dist[nx][ny]; // 최소 거리 갱신
							minX = nx; // 해당 X좌표 갱신
							minY = ny; // 해당 Y좌표 갱신
						} else if(minDist == dist[nx][ny]) { // 최소 거리인 물고기가 많다면?
							// 더 위에 있는 물고기 선택
							if(minX == nx) {
								// 그 위에 있는 물고기의 수가 많다면 가장 왼쪽에 있는 물고기 선택
								if(minY > ny) {
									minX = nx;
									minY = ny;
								}
							} else if(minX > nx) { // 더 위에 있는 물고기가 한 마리 라면
								minX = nx;
								minY = ny;
							}
						}
					}
					
					que.add(new Pos(nx, ny));
				}
			}
			
		}
	}
	
	// map 범위 안에 있는지?
	static boolean isArea(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < N;	
	}
	
	// 상어가 먹을 수 있는 물고기인지? -> 상어 사이즈보다 작아야 됨
	static boolean isEat(int x, int y) {
		return map[x][y] != 0 && map[x][y] < size;
	}
	
	// 상어가 해당 위치로 이동할 수 있는지? -> 해당 위치가 비어 있거나(0) 물고기가 있다면 상어보다 크기가 작아야 됨
	static boolean isAblePos(int x, int y) {
		return map[x][y] <= size;
	}
	
	static class Pos{
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}

정리

• 거리가 같은 물고기들 중 조건에 맞는 물고기부터 먹어야 하는 조건을 제대로 구현하지 못했다.
• while문 안에서 종료조건을 설정할 때 시간을 많이 낭비했다.