[BOJ/Java] 16236 : 아기 상어

문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

풀이

1. fish라는 클래스를 만들어 물고기의 위치와 아기상어로부터 떨어져있는 거리를 저장할 수 있도록 해준다
2. 아기상어의 위치부터 BFS를 사용해 물고기까지의 거리를 구한다/ 이 때 아기상어의 크기보다 큰 물고기는 지나가지 못하고 continue한다 / 아기상어의 크기보다 작은 물고기의 위치정보와 거리정보를 fish type으로 큐에 넣어 저장해둔다 
3. BFS가 끝나면 먹을 수 있는 물고기 리스트가 들어있는 큐를 꺼내보며 가장 가깝고, 가까운 것들 중에서는 가장 위에 있으며, 이 중에서는 가장 왼쪽인 target 물고기를 찾아낸다
4. target 물고기 위치로 아기상어를 옮겨준 뒤 target 물고기까지의 거리만큼 count를 더해준다
5. 더 이상 물고기가 없을 때까지 2부터 반복한다

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
	static int N, sharkX, sharkY;
	static int[][] map;
	static boolean[][] visit;
	static int size = 2, time, countForSize;
	static ArrayList<info> fishes = new ArrayList<>();
	static Queue<info> queue = new LinkedList<>();

	public static void main(String[] args) throws Exception {

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

			}
		}
		System.out.println(sharkX +", "+sharkY);
		
		visit = new boolean[N][N];
		while (true) {
			queue.offer(new info(sharkX, sharkY, 0));
			while (!queue.isEmpty()) {
				info temp = queue.poll();
				int x = temp.x;
				int y = temp.y;
				int dist = temp.dist;
				visit[x][y] = true;
				for (int d = 0; d < 4; d++) {
					int dx = x + dir[d][0];
					int dy = y + dir[d][1];

					if (dx < 0 || dy < 0 || dx >= N || dy >= N)
						continue;
					if(visit[dx][dy]) continue;
					
					if(map[dx][dy] > size) 
						continue;
					
					if(map[dx][dy] < size && map[dx][dy] != 0) {
						fishes.add(new info(dx, dy, dist+1));
						visit[dx][dy] = true;
						continue;
					}
					if(map[dx][dy] == size || map[dx][dy] == 0) {						
						queue.offer(new info(dx, dy, dist+1));
						visit[dx][dy] = true;
					}
					
				}
			}
			if(fishes.isEmpty()) {
				System.out.println(time);
				break;
			}
			
			info eatingFish = fishes.get(0);
			for(info f : fishes) {
				if(eatingFish.dist == f.dist) {
					if(eatingFish.x > f.x) {
						eatingFish = f;
					}
					else if(eatingFish.x == f.x) {
						if(eatingFish.y > f.y) {
							eatingFish = f;
						}
					}
				}
			}
			
			
			
			fishes.clear(); //먹을 수 있는 물고기 리스트 초기화
			time += eatingFish.dist;
			map[sharkX][sharkY] = 0;//현재 아기상어 위치를 0으로
			sharkX = eatingFish.x;
			sharkY = eatingFish.y;
			map[sharkX][sharkY] = 9;//옮겨간 아기상어 위치를 9로
			countForSize++;
			if(countForSize == size) { //먹은 물고기 개수가 상어의 몸 크기와 동일하면 몸크기가 +1 늘어남
				size++;
				countForSize = 0;
			}
			
			for(int i = 0; i < N; i++) {//bfs를 위한 방문배열 초기화
				for(int j = 0; j < N; j++) {
					visit[i][j] = false;
				}
			}

		}

	}

	static class info {//물고기의 위치와 거리정보를 담는 클래스
		int x, y, dist;

		public info(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
}

 

 

느낀점

물고기의 위치에 대한 정보를 저장해주는 info 클래스를 만들어주니 이후에 위치를 비교하거나 거리를 비교할 때 매우 편리했다