[백준 스터디 7주차] 16236번 아기상어 골드4 - 자바(JAVA) / 시뮬레이션/ 구현

📑 문제

 

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

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

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 상어가 한 번 움직이기 전에 먹을 수 있는 물고기까지의 거리를 최대로 초기화 시켜놓은 다음, 최소거리에 있는 물고기를 찾도록 했다. 물고기가 한 마리 발견되더라도 최소값은 갱신되기 때문에 코드가 잘 돌아간다.

 

✔️ 먹을 수 있는 물고기가 없을 때까지 무한 루프를 돌며 다음 먹이를 탐색한다

✔️ 다음 물고기까지의 거리(sharkD)를 MAX로 잡아놓고 bfs로 먹을 수 있는 물고기를 탐색하러 간다.

✔️ 거리가 제일 가깝고, 가장 왼쪽에 있는 물고기를 찾는다.

✔️ 탐색이 끝나고 물고기가 찾아졌으면(sharkD != MAX) 해당 물고기의 위치(sharkR, sharkC)로 상어위치를 업데이트 시켜준다.

✔️ 먹은 물고기의 개수를 카운트해준다. 이 때 개수가 상어 몸집과 같아졌으면, 상어 몸집을 키워주고 카운트는 다시 0이 된다.

✔️ 상어의 이동거리가 이동시간이 되므로, 물고기를 먹을 때마다 sharkD를 결과값에 더해준다.

 

 

 

 

 

 

 

 

🙋‍♀️ 의견

 삼성 기출로 엄청엄청 유명한 문제이다! 상어 저주의 시작을 끊어서..?

 파이썬 코드들은 엄청 깔끔하던데, 자바로 더 잘 할 수 있는지는 실력이 늘어봐야 알 것 같다ㅠㅠ

 시뮬레이션은 굳이 따로 설명할건 없고, 문제의 단계대로 차근차근 풀면 될 것 같다.

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_16236_아기상어_골드IV2 {
	
	static int[][] map;
	static int sharkR, sharkC, sharkD;
	static int N, size, result, MAX = 401;
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, 1, -1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int n = Integer.parseInt(st.nextToken());
				map[i][j] = n;
				if(n==9) {//shark
					sharkR = i;
					sharkC = j;
				}
			}
		}// input
		
		int cnt = 0;//먹은 물고기 개수
		size = 2;//시작크기
		while(true) {//one move
			if(cnt==size) {
				cnt = 0;
				size++;
			}
			
			map[sharkR][sharkC] = 0;
			sharkD = MAX;//먹을 수 있는 물고기까지의 거리를 최대로 초기화
			bfs(sharkR, sharkC);//탐색
			if(sharkD==MAX) break;//먹을 수 있는 물고기가 없다
			
			cnt++;
			result += sharkD;
		 }
		
		System.out.println(result);
	}// end of main
	
	static private void bfs(int sr, int sc) {
		
		boolean[][] visited = new boolean[N][N];
		visited[sr][sc] = true;
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] {sr, sc, 0});
		
		while(queue.size()>0) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			int d = cur[2];
			
			for (int i = 0; i < 4; i++) {
				//new position
				int nr = r+dr[i];
				int nc = c+dc[i];
				int nd = d+1;
				
				//exception
				if(nr<0 || nr>=N || nc<0 || nc>=N ||
					map[nr][nc]>size || visited[nr][nc]) continue;
				
				//move
				queue.offer(new int[] {nr, nc, nd});
				visited[nr][nc] = true;
				
				//detection
				if(map[nr][nc]>0 && map[nr][nc]<size) {
					//거리가 더 가까운 물고기 발견
					if(nd<sharkD) {
						sharkR = nr;
						sharkC = nc;
						sharkD = nd;					
					}
					//먼저 발견한 것과 거리가 같은 물고기 발견
					else if(nd==sharkD) {
						// 맨상단 맨좌측 물고기인 경우
						if(nr<sharkR || (nr==sharkR && nc<sharkC)) {
							sharkR = nr;
							sharkC = nc;
						}
					}
				}
			}//for loop
		}//queue
	}
}//end of class

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨