[Java Algorithm] 아기 상어 BOJ #16236

문제

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

16236번: 아기 상어

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_16236 {

	static int n;
	static int[][] map;
	static int[] start;
	static int cnt, shark, ans;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};

	public static int[] bfs(Deque<int[]> que, int[][] visited, int[] fish) {
		while(!que.isEmpty()) {
			int now[] = que.removeFirst();
			int x = now[0];
			int y = now[1];

			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if(nx < 0 || ny < 0 || nx >= n || ny >= n || map[nx][ny] > shark || visited[nx][ny] > 0) continue;
				visited[nx][ny] = visited[x][y] + 1;

				if(map[nx][ny] < shark && map[nx][ny] > 0) { // 상어보다 작은 물고기 만났을 때 => 기존에 먹으려고 했던 물고기보다 적합한지 확인 후, 먹을 물고기 업데이트
					if(fish[2] == 0 ||
							fish[2] > visited[nx][ny] ||
							(fish[2] == visited[nx][ny] && (fish[0] > nx || (fish[0] == nx && fish[1] > ny)))) {
						fish[0] = nx;
						fish[1] = ny;
						fish[2] = visited[nx][ny];
					}
				}

				que.add(new int[]{nx, ny});
			}
		}
		return fish;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(in.readLine());
		map = new int[n][n];

		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 9) start = new int[]{i, j}; // 아기 상어의 위치
			}
		}

		shark = 2;
		while(true) {
			Deque<int[]> que = new ArrayDeque<>();
			que.add(start);

			int[][] visited = new int[n][n];
			visited[start[0]][start[1]] = 1;
			map[start[0]][start[1]] = 0;

			int[] now = bfs(que, visited, new int[]{0, 0, 0});
			if(now[2] == 0) { // 더이상 먹을 물고기 없을 때
				System.out.println(ans);
				return;
			}

			ans += now[2]-1; // 물고기 먹는데 걸린 시간 누적
			cnt++; // 먹은 물고기 개수 누적
			if(cnt == shark) {
				cnt = 0;
				shark++; // 상어 크기만큼 물고기 먹으면 상어 크기 키워주기
			}
			map[now[0]][now[1]] = 0; // 방금 먹힌 물고기의 위치는 빈 칸으로 만들어주기
			start = Arrays.copyOf(now, 2); // 아기 상어의 위치를 방금 먹은 물고기 위치로 옮겨주기
		}
	}
}

👉 시뮬레이션 + BFS 문제

상어가 한 번 물고기를 먹을 때마다, bfs 탐색을 통해 최적의 물고기를 찾는 것을 반복해주는 식으로 구현

• main 메서드 안에서 while 반복을 통해 상어가 최적의 물고기를 찾는 과정을 표현했다.
  한 번의 while 실행 == 상어가 한 번 먹는 최적의 물고기 찾아 먹기
• start 배열에는 상어의 시작점이 저장되는데, que에 start 정보를 넣어주고
  visited와 map의 start 위치를 적절히 초기화시킨 후 bfs 탐색을 돌려주었다.
  (map은 이제 상어가 먹을 물고기 위치로 이동할 것이므로 0으로 초기화하고,
  visitied는 상어의 위치를 시작점으로 탐색할 것이므로 1로 초기화했다.)
• bfs 탐색은 특별한 점은 없으나, 확인해야 할 점은
  상어보다 작은 물고기를 만났다면, 기존에 먹으려고 했던 물고기보다
  더 적합한지(더 큰지) 확인 후, 먹을 물고기를 갱신해주는 부분,,!!
• 그리고 위의 갱신은 fish 배열을 통해 진행되는데, 이 fish 배열은 리턴되는 값으로,
  bfs 탐색 종료 시 이 배열을 통해 어떤 물고기를 먹을지, 혹은 먹을 물고기가 없었는지를 결정한다.
• bfs 메서드 종료 후, bfs 메서드가 반환한 fish 배열은 now라는 배열에 담아주었는데,
  now[2] 값이 0이라면 먹을 물고기가 없었다는 뜻이므로 ans를 출력하고 바로 리턴했다.
• 그 외의 경우에는 ans에 물고기를 먹는데에 걸린 시간인 now[2]-1을 더해주었고,
  cnt를 통해 먹은 물고기의 개수를 계속 누적해주었다.
  cnt 값이 상어의 크기와 같아지면 cnt는 다시 0으로 초기화, 상어의 크기는 1 늘렸다.
• 방금 먹은 물고기의 map 위치는 0으로 바꿔주었고,
  start 배열은 바뀐 상어의 위치로 초기화하여 다음부터 새로운 시작점에서 탐색할 수 있게 했다.

 

💡 피드백

• 죠금 복잡한,, 문제였지만!! 차근차근 이해하고 풀면 어려운 문제는 아니었다.