[삼성 SW 역량 테스트 기출 문제] 아기 상어 - 레벨2, 구현 + BFS + 최단거리

 

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

16236번: 아기 상어

 

아래코드는 아예 잘못푼 코드입니다.

문제를 온전하게 읽지 않아 생고생했습니다. 그것을 잊지않고자 틀린코드도 올렸습니다.

어떤 부분을 읽지 않았냐면 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

 

자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없습니다. 이전 문제인 치킨배달을 할떄 절대값을 사용해서 절대거리를 구한 것이 생각나어 그냥 아무생각없이 Math.abs를 사용하여 구한것이 문제였습니다. 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없으니 다른 방식을 이용하여 다시 작성해야합니다.

package Main;

import java.util.ArrayList;
import java.util.Scanner;

//다익스트라, BFS 같은 길찾기 알고리즘을 공부해야합니다.최단거리
public class Main {

	static int N;
	static int[][] map;
	
	static int[] dx = {};
	static int[] dy = {};
	static int time=0;
	static boolean simulateendflag = false;
	
	static Position shark;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		map = new int[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) {
					shark = new Position(i,j,2);
					shark.eatsum = 0;
				}
			}
		}
		
		simulate();
		System.out.println(time);
	}
	
	public static void simulate() {
		
		while(simulateendflag==false) {

			ArrayList<Position> caneatfishlist = new ArrayList<Position>();
			
			
			System.out.println("ToFindError sharkx sharky sharksize"+shark.x+" "+shark.y+" "+shark.size);
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					System.out.print(map[i][j] +" ");
					
					if(map[i][j] < shark.size && map[i][j] != 0 && map[i][j] != 9) {
						
//						System.out.println("map[i][j], sharksize sharkx shark y"+map[i][j]+" "+shark.size+" "+shark.x+" "+shark.y);
						
						caneatfishlist.add(new Position(i,j,map[i][j]));
					}
				}
				System.out.println();
			}
			
			System.out.println("caneatfishlist size:"+caneatfishlist.size());
			
			
			
			
			if(caneatfishlist.size() == 0) {
				simulateendflag = true;
				break;
			}
			
			
			boolean findfishflag = false;
			Position nearfishobject = new Position();
			int nearfishdistance = Integer.MAX_VALUE;
			for(int i=0;i<caneatfishlist.size();i++) {
				
				System.out.println("caneatfishlistindex, caneatfishlistx, caneatfishlisty:"+i+" "+caneatfishlist.get(i).x+" "+caneatfishlist.get(i).y);
				
				int distance = Math.abs(caneatfishlist.get(i).x - shark.x) + Math.abs(caneatfishlist.get(i).y - shark.y);				
				
				if(nearfishdistance > distance) {					
					findfishflag = true;
					nearfishdistance = distance;
					nearfishobject.x = caneatfishlist.get(i).x;
					nearfishobject.y = caneatfishlist.get(i).y;
					nearfishobject.size = map[caneatfishlist.get(i).x][caneatfishlist.get(i).y];
				}
			}
			
			//
			
			
			
			if(findfishflag == true) {
				System.out.println("x: y: map[][]"+nearfishobject.x+" "+nearfishobject.y+" "+map[nearfishobject.x][nearfishobject.y]);
				map[nearfishobject.x][nearfishobject.y] = 9;
				map[shark.x][shark.y]= 0; 
				
				time += Math.abs(nearfishobject.x - shark.x) + Math.abs(nearfishobject.y - shark.y);
				
				shark.x = nearfishobject.x;
				shark.y = nearfishobject.y;
				shark.eatsum += 1;
				
				if(shark.eatsum == shark.size) {
					shark.eatsum = 0;
					shark.size += 1;	
				}
				
			}
			
			
			
			
			
			/* 이렇게하지 말고 그때 그떄 가장 작은 값을 구해야 문제를 풀수 있습니다. 이유는 
			for(int i=0;i<fish.size()-1;i++) {
				for(int j=0;j<fish.size()-i;j++) {
					//거리가 먼것을 뒤로 보냅니다.
					int firstfishdistance = Math.abs(fish.get(j).x - shark.x) + Math.abs(fish.get(j).y - shark.y);
					int secondfishdistance = Math.abs(fish.get(j+1).x - shark.x) + Math.abs(fish.get(j+1).y - shark.y);
					if(firstfishdistance > secondfishdistance) {
						Position temp = new Position(fish.get(j).x, fish.get(j).y, fish.get(j).size);
						fish.get(j).x = fish.get(j+1).x;
						fish.get(j).y = fish.get(j+1).y;
						fish.get(j).size = fish.get(j+1).size;
						
						fish.get(j+1).x = temp.x;
						fish.get(j+1).y = temp.y;
						fish.get(j+1).size = temp.size;
					}
				}
			}
			*/

		}
		
	}


	
}


class Position implements Comparable<Position>{
	int x;
	int y;
	int size;
	int eatsum;	//for shark
	public Position() {
		
	}
	public Position(int x, int y, int size) {
		this.x=x;
		this.y=y;
		this.size=size;
		eatsum = 0;
	}
	
	//Collections.sort로 마무리
	@Override
	public int compareTo(Position other) {
		   
		//오름차순으로 정렬, 생각방법은 other이 더 클때 return 1이라면 더 큰 other이 앞으로 가므로 내림차순이 될것임.
		//우리는 더 작을때 return 1을 함으로써 other이 더 뒤로 가도록 하는방법
		if(this.x > other.x && this.y > other.y) {
			return 1;
		}else if(this.x == other.x && this.y == other.y) {
			return 0;
		}else if(this.x < other.x && this.y < other.y) {
			return -1;
		}
		
		return 1;
	}
	
	
}

 

 

BFS를 사용하여 올바르게 푼 방식입니다.

이 방식에서 또한 생각하지 못했던 부분은 

https://www.acmicpc.net/board/view/93917

글 읽기 - 다음 예외 케이스 고려하시면 통과하실 수 있습니다.

이 사이트의 예외케이스 중 아래의 반례케이스를 해결하지 않았었습니다.

3
0 1 1
4 4 4
0 9 0

 

첫번째

-위의 반례케이스를 보면 4 4 4 로 막혀서 상어가 먹이의 위치를 보더라도 bfs에서 해당 위치를 방문하지 않았다면 방문할 수 없는 장소이기에 포함하면 안됩니다. 해결방안으로 int[][] distancemap = bfs(shark.x, shark.y, shark.size); 를 먼저 실행하여 상어가 갈 수 있는 모든 곳의 최단거리를 먼저 계산한뒤, 모든 map을 돌면서 상어가 먹을 수 있는 곳 위치를 구할때 visited[i][j] 가 true일때만 arraylist에 넣을 수 있도록 하였습니다.

 

두번째-두번째는 위의에서와 마찬가지로 문제를 처음에 자신보다 큰 물고기가 있는 자리는 침범하지 못한다라는 것을 읽지 못하여 멍청하게 Math.abs를 통하여 절대거리를 바로 구한 것이 문제였습니다.

 

세번째-BFS를 통하여 최단거리를 찾는 과정이 처음이었습니다. Queue를 통하여서 진행하였는데 제가 정리해놓은 BFS 관련 문서를 보고 구현할 수 있었습니다. 다음에는 혼자서 해보도록 합니다.

 

 

 

package Main;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//최단경로를 구하는 다익스트라 알고리즘을 사용해야합니다.
//혹은 BFS? 를 공부
public class Main {

	static int N;
	static int[][] map;
	
	//동,남,서,북 (시계방향 회전)
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	static int time=0;
	static boolean simulateendflag = false;

	static boolean[][] visited;
	static Position shark;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) {
					shark = new Position(i,j,2);
					shark.eatsum = 0;
				}
			}
		}
		
		simulate();
		System.out.println(time);
	}
	
	public static int[][] bfs(int sharkx, int sharky, int sharksize) {
		
		Queue<Position> q = new LinkedList<Position>();
		int[][] distancemap = new int[N][N];

		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				visited[i][j] = false;
			}
		}
		
		visited[sharkx][sharky] = true;		
		
		q.offer(new Position(sharkx, sharky, sharksize));
		//큐가 빌떄까지 반복
		while(!q.isEmpty()) {
			Position temp = q.poll();
//			System.out.println(temp.ToString());
			int distancecnt = distancemap[temp.x][temp.y];
			for(int i=0;i<4;i++) {
				int nx = temp.x + dx[i];
				int ny = temp.y + dy[i];
				
				if(nx >= 0 && nx <= N-1 && ny >= 0 && ny <= N-1) {
					if(visited[nx][ny] == false && map[nx][ny] <= sharksize) {
						q.offer(new Position(nx, ny, sharksize));
						visited[nx][ny] = true;
						distancemap[nx][ny] = distancecnt+1;
					}
				}
			}
		}
		
		return distancemap;
		
	}
	
	public static void simulate() {
		
		while(simulateendflag==false) {

			ArrayList<Position> caneatfishlist = new ArrayList<Position>();
//			System.out.println("ToFindError sharkx sharky sharksize"+shark.x+" "+shark.y+" "+shark.size);
			
			int[][] distancemap = bfs(shark.x, shark.y, shark.size);			
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
//					System.out.print(map[i][j] +" ");
					
					if(map[i][j] < shark.size && map[i][j] != 0 && map[i][j] != 9 && visited[i][j] == true) {
//						System.out.println("map[i][j], sharksize sharkx shark y"+map[i][j]+" "+shark.size+" "+shark.x+" "+shark.y);						
						caneatfishlist.add(new Position(i,j,map[i][j]));
					}
				}
//				System.out.println();
			}
			
//			System.out.println("caneatfishlist size:"+caneatfishlist.size());
			
			if(caneatfishlist.size() == 0) {
				simulateendflag = true;
				break;
			}
			

			
			
			boolean findfishflag = false;
			Position nearfishobject = new Position();
			int nearfishdistance = Integer.MAX_VALUE;
			for(int i=0;i<caneatfishlist.size();i++) {
				
//				System.out.println("caneatfishlistindex, caneatfishlistx, caneatfishlisty:"+i+" "+caneatfishlist.get(i).x+" "+caneatfishlist.get(i).y);				
//				int distance = Math.abs(caneatfishlist.get(i).x - shark.x) + Math.abs(caneatfishlist.get(i).y - shark.y);				
				int distance = distancemap[caneatfishlist.get(i).x][caneatfishlist.get(i).y];

				if(nearfishdistance > distance) {					
					findfishflag = true;
					nearfishdistance = distance;
					nearfishobject.x = caneatfishlist.get(i).x;
					nearfishobject.y = caneatfishlist.get(i).y;
					nearfishobject.size = map[caneatfishlist.get(i).x][caneatfishlist.get(i).y];
				}
			}
			
			//
			
			
			
			if(findfishflag == true) {
//				System.out.println("x: y: map[][]"+nearfishobject.x+" "+nearfishobject.y+" "+map[nearfishobject.x][nearfishobject.y]);
				map[nearfishobject.x][nearfishobject.y] = 9;
				map[shark.x][shark.y]= 0; 
				
//				time += Math.abs(nearfishobject.x - shark.x) + Math.abs(nearfishobject.y - shark.y);
				time += distancemap[nearfishobject.x][nearfishobject.y];
				
				shark.x = nearfishobject.x;
				shark.y = nearfishobject.y;
				shark.eatsum += 1;
				
				if(shark.eatsum == shark.size) {
					shark.eatsum = 0;
					shark.size += 1;	
				}
				
			}
			
		

		}
		
	}


	
}


class Position{
	int x;
	int y;
	int size;
	int eatsum;	//for shark
	public Position() {
		
	}
	public Position(int x, int y, int size) {
		this.x=x;
		this.y=y;
		this.size=size;
		eatsum = 0;
	}
	
	public String ToString() {
		return "x:"+ this.x + " y"+ this.y + " size" + this.size + " eatsum" + this.eatsum;
	}
}