[Java/Simulation] 백준 16236. 아기상어

🤔 Intuition

시뮬레이션 문제인 것은 확실하나, 탐색을 어떻게 할지 고민하였다.

 

우선되는 먹이의 조건이 (1) 거리가 가까울 것 (2) row가 작을 것 (3) column이 작을 것 이었으므로 델타탐색을 "상 좌 우 하" 로 하면서 가장 먼저 나오는 먹이를 낼름 먹어버리면 될 것으로 봤다.

 

하지만 위는 틀렸다.

 

위의 경우에는 항상 거리값이 가장 가까운 먹이를 찾을 수 있지만, 바로 만난 먹이가 가장 위에 있고, 가장 왼쪽에 있다는 것을 보장할 수 없다. 아래 예시를 보면 이해가 가능하다.

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

. . 1 . .
. 2 x 3 .
4 x C x 6
. 5 x 7 .
. . 8 . .

 

C 지점에서 상 좌 우 하 방식으로 탐색을 했을 때, 2번째 칸들의 탐색 순서를 위와 같이 나타낼 수 있다. 여기서 포인트는 4번 뒤에 6번이 5번이 되어야 하지만, 탐색 순서상 아래 좌표가 우선적으로 탐색되게 된다는 걸 알 수 있다.

 

따라서 이를 해결하기 위해서 가장 단순한 방법은 우선순위 큐를 이용하는 것이다. BFS는 어차피 큐를 이용하니까, 조건에서 안내하는 우선순위를 우선순위큐의 정렬조건으로 세팅해 준 뒤 이를 이용하여 BFS 탐색을 하는 방법이 가장 직관적이다.

🔎 Algorithm & Complexity

* @algorithm simulation (bfs)
* @time O(N^2 * log(N^2)) : 우선순위큐 BFS 시 맵의 모든 칸이 큐에 들어가면서 O(N^2) * 우선순위큐 연산시 O(logN^2) -> 144 ms
* @memory O(N^2) -> 14572 KB

👨🏻‍💻 Logic

상어 위치로부터 BFS 탐색을 통해 target을 찾는다. 이 과정에서 우선순위 큐를 이용하여 문제에서 제시하는 우선순위 조건을 준수한다.

 

*** 여기서 본인은 처음에 visited 체크를 Queue에서 poll할 때 해줬었다. 이렇게 로직을 구성했을 때에는 Memory Limit Exceeded 가 발생했다. 그 이유는 Queue 자료구조에서 해당 좌표가 뽑힐 때까지 visited 처리를 하지 않아서, 다른 좌표에서도 해당 좌표를 갈 수 있다고 판단하고 queue에 계속 중복된 좌표를 담아내게 되기 때문이다. 특히나 우선순위 큐로 구성하게 되면 더더욱 중복이 많이 발생할 수 있게 된다. 따라서 BFS를 사용할 때에는 반드시 push할 때 visited를 체크해줘야 한다. (평소에 이렇게 하지 않긴 했는데, 왜 그렇게 해왔는지 이유는 몰랐던 것 같다. 이번 기회에 생각해볼 수 있는 계기가 되어서 좋았다.)

public class BOJ_16236_아기상어 {
    private static int N, ans, cnt, sharkSize, sharkY, sharkX;
    private static int[][] map;
    private static boolean hasTarget;
    private static int[] dy = {-1, 0, 0, 1};
    private static int[] dx = {0, -1, 1, 0};
    private static int[] visited;
    private static int[][] step;
    private static Queue<int[]> q = new PriorityQueue<>(((o1, o2) -> {
        if (o1[2] == o2[2]) {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }
        return o1[2] - o2[2];
    }));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        step = new int[N][N];

        int num;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                num = Integer.parseInt(st.nextToken());
                if (num == 9) {
                    sharkY = i;
                    sharkX = j;
                    continue;
                }
                map[i][j] = num;
            }
        }

        sharkSize = 2;

        do {
            hasTarget = bfs();
        } while (hasTarget);

        br.close();
        bw.write(sb.append(ans).toString());
        bw.flush();
        bw.close();
    }
    private static boolean bfs() {
        q.clear();
        q.add(new int[]{sharkY, sharkX, step[sharkY][sharkX]});
        visited = new int[N];
        visited[sharkY] |= 1 << sharkX;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int y = now[0];
            int x = now[1];

            if (map[y][x] != 0 && map[y][x] < sharkSize) { // 잡아먹을 수 있는 경우
                cnt++;
                if (cnt == sharkSize) {
                    sharkSize++;
                    cnt = 0;
                }

                map[y][x] = 0;
                ans = step[y][x];
                sharkY = y;
                sharkX = x;
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (canGo(ny, nx)) {
                    step[ny][nx] = step[y][x] + 1;
                    visited[ny] |= 1 << nx;

                    q.add(new int[]{ny, nx, step[ny][nx]});
                }
            }
        }
        return false;
    }

    private static boolean canGo(int y, int x) {
        return inRange(y, x) && map[y][x] <= sharkSize && (visited[y] & (1 << x)) == 0;
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < N;
    }
}

 

🔥Other's insight

다른 사람은 우선순위 큐를 굳이 사용하지 않고, BFS 탐색을 매번 쭉 돌면서 먹잇감까지의 거리와 좌표를 갱신해주면서 진행하였다. 진정으로 완탐을 진행하였지만, 오히려 우선순위 큐를 사용할 때 발생하는 불필요한 정렬 연산이 들어가지 않아 실행시간이 더욱 단축되었다. 

 

사실 위 로직보다 아래 로직이 더 군더더기 없고 명료한 코드로 느껴진다. 이 코드를 보니, 내가 평소에 너무 돌아가게 생각하고 있는 건 아닌지 반성하게 된다.

/**
* @time 88 ms
* @memory 12280 KB
*/
public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[][] board;
	static BabyShark babyShark;
	static int eatCnt;
	static int ans;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	
	static boolean check_range(int y, int x) {
		return y >= 0 && x >= 0 && y < N && x < N;
	}
	
	static boolean bfs() {
		Queue<Node> q = new ArrayDeque<Node>();
		q.add(new Node(babyShark.y, babyShark.x, 0));
		
		board[babyShark.y][babyShark.x] = 0;
		
		boolean [][]visited = new boolean[N][N];
		visited[babyShark.y][babyShark.x] = true;
		
		boolean eat = false;
		
		int eatY = 0, eatX = 0;
		int minDist = Integer.MAX_VALUE;
	
		
		while(q.size() > 0) {
			
			Node cNode = q.poll();
			int y = cNode.y;
			int x = cNode.x;
			int depth = cNode.depth;
			
			
			if(eat && minDist < depth) {
				break;
			}
			
			// 먹을 수 있는 먹이라면
			if(board[y][x] > 0 && board[y][x] < babyShark.size) {
				if(!eat) {
					eat = true;
					minDist = depth;
					eatY = y;
					eatX = x;
				}else {
					if(y < eatY || (y == eatY && x < eatX)) {
						eatY = y;
						eatX = x;
					}
				}
				continue;
			}
			
			for(int i = 0; i < 4; i++) {
				int ny = y + dir[i][0];
				int nx = x + dir[i][1];
				
				// 현재 상어 사이즈보다 작다면 
				if(check_range(ny, nx) && !visited[ny][nx] && board[ny][nx] <= babyShark.size) {
					visited[ny][nx] = true;
					q.add(new Node(ny, nx, depth + 1));
				}
			}
		}
		
		if(eat) {
			eatCnt++;
			ans += minDist;
			babyShark.y = eatY;
			babyShark.x = eatX;
			
			if(eatCnt == babyShark.size) {
				eatCnt = 0;
				babyShark.size++;
			}
			
			return true;
		}
		
		return false;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int k = 0; k < N; k++) {
				board[i][k] = Integer.parseInt(st.nextToken());
				
				if(board[i][k] == 9) {
					babyShark = new BabyShark(i, k, 2);
				}
			}
		}
		
		while(true) {
			if(!bfs()) break;
		}
		
		System.out.println(ans);

	}
	
	static class Node{
		int y;
		int x;
		int depth;
		Node(int y, int x, int depth){
			this.y = y;
			this.x = x;
			this.depth = depth;
		}
	}
	
	static class BabyShark{
		int y;
		int x;
		int size;
		
		BabyShark(int y, int x, int size){
			this.y = y;
			this.x = x;
			this.size = size;
		}
	}

}