[BOJ 16236] 아기 상어

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

16236번: 아기 상어

 

https://www.youtube.com/watch?v=761ae_KDg_Q

 

문제 푸는 내내 이 노래가 머릿속에 맴돌았다

아기상어... 용서하지 않겠어..........

 

홈페이지에서 정답률은 36퍼라고 나오는데, 체감상 다른 역테 기출보다 어려운듯?

놀면서 풀긴 했지만 거의 하루 넘게 이 문제만 풀었고 다른 질문들 보면서 겨우겨우 풀어냄ㅠㅠ

 

조건이 조금 많이 까다로운데, 특히 가장 많이 헷갈렸던 것이 거리가 가장 가까운 물고기를 먹는 조건이었다.

거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다는게 조건인데

 

0 0 0 1

0 0 0 0

0 1 0 9

0 0 0 0

 

이 상태에서 (3, 0)을 먼저 먹고, (1, 3)을 두번째로 먹는 것이 올바른 해법이다.

문제 설명이 조금만 더 친절했다면 좋았겠지만 예제를 통해서 문제 조건을 이해하는 것도 알고리즘 풀이에서 중요한 작업일 거라고 생각하며 화를 가라앉히기로 했다 ...^^;

 

사용한 알고리즘은 BFS

현재 아기 상어의 위치를 기준으로 BFS를 돌려서, 먹이가 탐색된 경우 candidate 라는 큐에 삽입한다.

map 객체는 물고기들의 위치 정보를 포함한 지도이다.

q에 탐색 대상을 삽입할 때마다 새로운 Fish 객체를 생성했는데, movetime(물고기가 얼마나 이동했는지)를 유지하기 위해서 이런 방식을 취했다.

for(int i = 0 ; i < fishnum ; i++){
			Queue <Fish> q = new LinkedList<Fish>();
			Queue<Fish> candi = new LinkedList<Fish>();
			int[][] v = new int[N][N];
			q.add(shark);
			
			int cx = shark.x;
			int cy = shark.y;
			
			while(!q.isEmpty()){
				Fish cur = q.poll();
				
				if(map[cur.y][cur.x].isFish && shark.canEat(map[cur.y][cur.x])){
					map[cur.y][cur.x].locx = cx - map[cur.y][cur.x].x;
					map[cur.y][cur.x].locy = cy - map[cur.y][cur.x].y;
					map[cur.y][cur.x].movetime = cur.movetime;
					candi.add(map[cur.y][cur.x]);
					continue;
				}
				
				for(int j = 0 ; j < 4 ; j++){
					if(cur.move(j, N, map)){
						if(v[cur.y][cur.x] == 0){
							q.add(new Fish(cur.x, cur.y, cur.size, false, cur.movetime));
							v[cur.y][cur.x] = 1;
						}
						cur.back(j, N);
					}
				}
			}

 

그리고 Fish 클래스는 다음과 같이 정의했다. isFish는 상어이거나, 이미 먹힌 물고기인 경우 false로 설정된다(비직관적이어서 죄송...)

길어서 생략했지만 if(cur.move(....)) 를 통해서 해당 객체가 한 칸 이동하므로, back 메소드를 정의해 다시 되돌릴 수 있도록 구현했다. move 메소드는 움직이지 못할 경우에는 좌표 변화가 없으므로, 그 경우 back을 해 줄 필요는 없다.

 

class Fish{
	int x, y;
	int eatnum;
	int size;
	int movetime;
	boolean isFish;
	int locx;
	int locy;
	
	int[] xd = {0, -1,+1 ,0}; // left up right down
	int[] yd = {-1,0,0, +1};

	
	public Fish(int x, int y, int size, boolean isFish, int movetime){
		this.x = x;
		this.y = y;
		this.size = size;
		this.isFish = isFish;
		this.movetime = movetime;
		this.locx = 0;
		this.locy = 0;
	}
	public void eat(){
		eatnum++;
	}
	public void growup(){
		if(eatnum == size){
			size++;
			eatnum = 0;
		}
	}
	public void reset(){
		this.isFish = false;
		this.size = 0 ; 
	}
	
	public boolean canEat(Fish fish){
		if ( fish.isFish) {
			if(fish.size < this.size ){
				return true;
			}
		}
		return false;
	}
	
	public boolean move(int dir, int N, Fish[][] map){
		int tmpx = x;
		int tmpy = y;
		tmpx = x + xd[dir];
		tmpy = y + yd[dir];
		if(tmpx == -1 || tmpy == -1 || tmpx == N || tmpy ==N){
			return false;
		}
		else if(this.size < map[tmpy][tmpx].size){
			return false;
		}
		else{
			this.x = tmpx;
			this.y = tmpy;
			movetime++;
			return true;
		}
	}

			Fish tmp = candi.poll();
			
			while(!candi.isEmpty()){
			
				
				Fish tmp2 = candi.poll();
				if(tmp.movetime == tmp2.movetime){
					if(tmp2.y <  tmp.y){
						tmp = tmp2;
					}
					else if(tmp.y == tmp2.y){
						if(tmp2.x <  tmp.x) {
							tmp = tmp2;
						}
					}
				}else if(tmp.movetime > tmp2.movetime){
					tmp = tmp2;
				}
			}

마지막으로 위치를 비교하는 코드인데, 거리가 가깝다는 것은 현재 상어로부터 movetime이 동일하다는 것을 의미한다. 따라서 비교하고자 하는 두 후보 물고기의 movetime이 같은 경우, y좌표를 먼저 비교하고, x 좌표를 비교한다(이 부분을 처음에 잘못 이해하는 바람에... 거의 반나절을 씨름했다ㅠㅠ)

 

처음부터 문제를 잘 이해하고 코드를 짰다면 이렇게 복잡한 코드가 되지 않았을 거라는 아쉬움이 남는다ㅠㅠ

창피해서 올리지 않을 생각이었는데, 이렇게라도 부끄러움을 느끼지 않으면 또 다시 같은 행동을 반복할 것 같아서 반성하는 의미에서 게시하려고 한다ㅠ