[백준] 16236 아기상어

1. 문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

2. 접근방법

아기상어가 물고기를 잡아먹으며 몇 초동안 있을 수 있는지 찾아보는 문제

 

bfs가 버무려진 시뮬레이션 문제이다.

 

 

이 조건에 맞추면서 가장 가까운 물고기를 찾을 때 bfs를 사용한다.

 

나머지 부분은 시키는대로만 구현하면 되니 넘어가고

 

bfs로 거리를 1씩 증가시키면서 상어와 거리가 동일한 위치 전부다 검사하고 먹을 물고기가 있다면

배열에 저장 시켜뒀다가 위 조건에 맞춰 한 마리만 꺼내 먹는다.

꺼내 먹을때 거리 만큼 시간+ 시켜주고

 

이후 먹은 갯수에 따라 size에도 변화를 주고 하면서 시뮬레이션을 돌다가

먹을 물고기를 하나도 못찾게 되면 종료하면 된다. 

 

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class P16236아기상어 {
	static int map[][], time, size, N, sizeup;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		size = 2;
		sizeup = size;
		Point now = null;
		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) {
					now = new Point(i, j);
					map[i][j] = 0;
				}
			}
		}

		while (true) {
			Point food = find(now);
			if (food == null) {
				break;
			}
			map[food.x][food.y] = 0;
			now = food;

			sizeup--;
			if (sizeup == 0) {
				sizeup = ++size;
			}

		}
		System.out.println(time);
	}

	static Point find(Point start) {
		Queue<Point> que = new LinkedList<Point>();
		que.offer(start);
		int dr[] = { 1, -1, 0, 0 };
		int dc[] = { 0, 0, 1, -1 };
		boolean visited[][] = new boolean[N][N];
		visited[start.x][start.y] = true;
		List<Point> foodlist = new ArrayList<Point>();
		int dist = 1;
		while (!que.isEmpty()) {
			for (int queSize = que.size(); queSize > 0; queSize--) {
				Point now = que.poll();
				for (int i = 0; i < 4; i++) {
					int row = now.x + dr[i];
					int col = now.y + dc[i];

					if (row < 0 || col < 0 || row >= N || col >= N)
						continue;
					if (map[row][col] > size)
						continue;

					if (visited[row][col])
						continue;
					if (map[row][col] != 0 && map[row][col] < size) {
						foodlist.add(new Point(row, col));
					}
					visited[row][col] = true;
					que.offer(new Point(row, col));

				}
			}
			if (foodlist.size() != 0) {
				Collections.sort(foodlist, new Comparator<Point>() {
					@Override
					public int compare(Point o1, Point o2) {
						if (o1.x == o2.x)
							return o1.y - o2.y;
						return o1.x - o2.x;
					}
				});
				time += dist;

				return foodlist.get(0);
			}
			dist++;
		}

		return null;
	}

}

4. 마치며

물고기와 가장 가까운 먹을 수 있는 물고기를 찾는게 가장 중요했던 문제

bfs의 개념을 알고 있었다면 쉽게 구현 가능할 것이다.