[ 백준 16236번 아기 상어 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

 

(삼성전자 서류 통과해서 코딩테스트 준비를 해야하는데,,,,

다른 기업들 면접이랑 너무 많이 겹쳐서 준비를 많이 못했었다 ㅜㅜ)

 

2주 남은 지금부터라도 다시 한 번 문제를 열심히 풀어보려고 합니다!

이번 문제는 백준 16236번 아기 상어 문제입니다.

기존의 BFS를 약간 변형해야 하는 문제라 신선하게 다가왔고, 조건이 많아서 까다로운 문제였던 것 같습니다.

 

 

문제보기

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

16236번: 아기 상어

 

나의 풀이

 

아기 상어가 물고기를 먹는 규칙은 다음과 같습니다. 자기보다 크기가 작은 물고기를 먹되, 1) 거리가 가까운 순으로 먹고!, 거리가 가까운 물고기가 여러 개 존재한다면 2) 가장 위쪽에, 그리고 3) 가장 왼쪽에 있는 물고기 순서대로 먹습니다. 그러므로 조건이 3개입니다.

 

거리가 가장 가까운 물고기를 탐색하기 위해서 BFS를 이용합니다! BFS는 너비 우선 탐색이니 거리를 기준으로 한 탐색을 할 때 유용한 알고리즘입니다.

 

그런데! 그냥 BFS를 사용하면 안되고 살짝 변형을 주어야 합니다.

 

BFS에서 큐가 작동하는 원리는 들어온 순대로 반환(즉, 거리가 짧은 순서대로 반환)하게 됩니다. 그런데 해당 문제에서는 거리가 같은 경우에 가장 위쪽, 가장 왼쪽 물고기를 반환한다는 추가 조건이 있으므로! 우선순위 큐를 새롭게 정의해서 구현해주어야 합니다. 그래서 저의 경우에는,

 

static class Point implements Comparable<Point> {
		int i;
		int j;
		int cnt;

		Point(int i, int j, int cnt) {
			this.i = i;
			this.j = j;
			this.cnt = cnt;
		}

		public int compareTo(Point p) {
			if (this.cnt < p.cnt) {
				return -1;
			} else if (this.cnt == p.cnt) {
				if (this.i < p.i) {
					return -1;
				} else if (this.i == p.i) {
					if (this.j < p.j) {
						return -1;
					} else if (this.j == p.j) {
						return 0;
					} else {
						return 1;
					}
				} else {
					return 1;
				}
			} else {
				return 1;
			}
		}
	}

 

다음과 같이 Comparable 클래스의 compareTo 메소드를 재정의해주었습니다!

 

그리고 또 한 가지 주의할 점이 있습니다.

 

처음 아기 상어 위치에서 BFS 탐색을 통해 먹을 물고기를 발견하면, 물고기를 먹은 다음 방문 여부를 저장했던 c 배열(일반적으로 많은 사람들은 visited라고 이름을 짓더군요,,)과 우선순위 큐를 초기화 해주어야 합니다!

 

왜냐하면 한 번 물고기를 먹은 다음에는 그 위치에서 새롭게 bfs 탐색을 해주어야 하기 때문에 이전에 방문했던 여부를 저장했던 배열과 큐를 싹 비워주어야 합니다.

 

 

코드

//bfs 문제

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

public class N_16236 {
	static class Point implements Comparable<Point> {
		int i;
		int j;
		int cnt;

		Point(int i, int j, int cnt) {
			this.i = i;
			this.j = j;
			this.cnt = cnt;
		}

		public int compareTo(Point p) {
			if (this.cnt < p.cnt) {
				return -1;
			} else if (this.cnt == p.cnt) {
				if (this.i < p.i) {
					return -1;
				} else if (this.i == p.i) {
					if (this.j < p.j) {
						return -1;
					} else if (this.j == p.j) {
						return 0;
					} else {
						return 1;
					}
				} else {
					return 1;
				}
			} else {
				return 1;
			}
		}
	}

	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int N = Integer.parseInt(br.readLine());
			int[][] A = new int[N][N];

			int babySize = 2;
			int babyi = 0;
			int babyj = 0;
			int ate = 0; // 아기 상어 크기 커지는 것을 계산하기 위한 변수
			int time = 0;

			for (int i = 0; i < N; i++) {
				String[] arr = br.readLine().split(" ");
				for (int j = 0; j < N; j++) {
					A[i][j] = Integer.parseInt(arr[j]);
					if (A[i][j] == 9) {
						babyi = i;
						babyj = j;
					}
				}
			}

			int[][] c = new int[N][N]; // 방문 여부 저장
			PriorityQueue<Point> pq = new PriorityQueue<Point>();

			c[babyi][babyj] = 1;
			pq.offer(new Point(babyi, babyj, 0));
			A[babyi][babyj] = 0; // 이 부분 때문에 테케 오류 났음. 아기상어의 처음 위치는 0으로 바꾸어주어야함.

			while (!pq.isEmpty()) {
				Point p = pq.poll();

				if (A[p.i][p.j] < babySize && A[p.i][p.j] != 0) {
					if (time < p.cnt)
						time = p.cnt;

					ate++;
					A[p.i][p.j] = 0;
					c = new int[N][N];
					pq.clear();

					if (ate == babySize) {
						ate = 0;
						babySize++;

					}

				}
				for (int i = 0; i < dx.length; i++) {
					if (p.i + dx[i] >= 0 && p.i + dx[i] < N && p.j + dy[i] >= 0 && p.j + dy[i] < N) {
						if (A[p.i + dx[i]][p.j + dy[i]] <= babySize && c[p.i + dx[i]][p.j + dy[i]] == 0) {
							c[p.i + dx[i]][p.j + dy[i]] = 1;
							pq.offer(new Point(p.i + dx[i], p.j + dy[i], p.cnt + 1));
						}
					}
				}
			}
			System.out.println(time);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

채점 pass!

 

p.s) 혹시나 테케 3, 4번 오류 나시는 분들은 처음 아기 상어의 위치에 있던 9를 이동 후 0으로 바꾸어 주었는지 확인해주세요! (는 제 얘기,,,)