백준 16236 아기 상어 - 삼성 SW 역량 테스트 기출

백준 16236 아기 상어 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

16236번: 아기 상어

 

2. 문제 해결에 대한 아이디어

1. 상어가 움직임을 멈추는 경우는 두 가지가 있다.

   . 모든 물고기를 먹은 경우

   . 자기보다 크기가 크거나 같은 물고기만 남은 경우

2. 상어의 위치를 기준으로 BFS 하여 처음 물고기를 만나는 거리(비용)을 minDist에 저장한다.

3. 업데이트 된 minDist와 같은 거리에 있는 물고기들의 위치를 candi에 저장한다.

4. BFS 가 끝난 후에, 가장 좌측 상단에 있는 물고기 위치를 얻기 위해 행과 열 기준으로 candi를 sorting한다.

5. candi의 첫 번째 값이 먹힐 물고기이다.

6. 먹고 난 후에는 상어의 위치, 죽은 물고기 수, 경험치, 크기, 보드 내 숫자 수정, 총 시간 추가 등을 진행한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static class Fish {
		int y, x;
		int size;
		int exp;

		public Fish(int y, int x, int size, int exp) {
			super();
			this.y = y;
			this.x = x;
			this.size = size;
			this.exp = exp;
		}

	}

	static class Pair implements Comparable<Pair> {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public int compareTo(Pair o) {
			if (this.y == o.y)
				return this.x - o.x;
			return this.y - o.y;
		}

	}

	static int N;
	static int[][] board;
	static int[][] visit;
	static Fish shark;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int fishCnt = 0;
	static int deadCnt = 0;
	static int time = 0;

	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\아기상어_16236\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().split(" ")[0]);
		board = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] == 9) {
					shark = new Fish(i, j, 2, 0);
				} else if (board[i][j] != 0) {
					fishCnt++;
				}
			}
		}

		while (deadCnt != fishCnt) {
			if (!sharkMove())
				break;

		}

		System.out.println(time);

	}

	public static boolean sharkMove() {
		int minDist = -1;
		visit = new int[N][N];
		Queue<Pair> q = new LinkedList<>();
		ArrayList<Pair> candi = new ArrayList<>();
		visit[shark.y][shark.x] = 1;
		q.add(new Pair(shark.y, shark.x));
		while (!q.isEmpty()) {
			Pair now = q.poll();
			int y = now.y;
			int x = now.x;
			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];

				if (yy >= N || xx >= N || yy < 0 || xx < 0 || visit[yy][xx] != 0 || board[yy][xx] > shark.size)
					continue;

				visit[yy][xx] = visit[y][x] + 1;
				if (board[yy][xx] != 0 && board[yy][xx] != 9 && board[yy][xx] < shark.size) {
					if (minDist == -1) {
						minDist = visit[yy][xx];
						candi.add(new Pair(yy, xx));
					} else {
						if (minDist == visit[yy][xx]) {
							candi.add(new Pair(yy, xx));
						}
					}
				}
				q.add(new Pair(yy, xx));
			}
		}

		if (candi.isEmpty())
			return false;

		Collections.sort(candi);

		Pair target = candi.get(0);
		board[shark.y][shark.x] = 0;
		board[target.y][target.x] = 9;
		++deadCnt;
		shark.y = target.y;
		shark.x = target.x;
		++shark.exp;
		if (shark.exp == shark.size) {
			shark.exp = 0;
			++shark.size;
		}
		time += --minDist; // 제자리 비용이 1이어서 보정

		return true;

	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 삼성 기출 중 쉬운 편에 속한다.