[BOJ]16236 -아기 상어(G3)

suhyun·2023년 1월 31일
0

백준/프로그래머스

목록 보기
67/81

문제 링크

16236-아기 상어


입력

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

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

0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.

출력

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


문제 풀이

진짜 조건이 많아도 너무 많다..

이동 조건

  1. 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음
  2. 자신의 크기보다 큰 물고기만 먹을 수 있음
  3. 크기가 같은 물고기는 먹을 수 없지만, 그 칸을 지가갈 수는 있음

먹는 조건

  1. 먹을 수 있는 물고기가 1마리라면, 먹으러 간다.
  2. 1마리 보다 많다면?
    1) 거리가 상어와 가까운 순으로 먹으러 이동 -> 지나야하는 칸의 갯수가 최소값
    2) 거리가 가까운 물고기가 여러마리라면? -> 가장 위에있는 물고기부터
    가장 위에 있는 물고기도 여러마리라면? -> 가장 왼쪽에 있는 물고기부터

우선은 가중치가 1인 그래프에서의 최단거리이기때문에 bfs 로 결정
코드에 대한 세세한 설명은 주석으로 처리해 표기해두었다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
    int x, y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    static int N;
    static int[][] maps, dist;    // 0: 빈칸, 9: 상어의 위치, 1~6: 칸에 있는 물고기 크기
    static int minDist,minX, minY;

    static int sharkSize = 2;
    static int sharkX = 0, sharkY = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

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

        int cnt = 0;
        int eat = 0;
        while (true) {
        
            // dist[][]는 방문 여부 체크와 함께 시작점에서 해당 좌표까지의 거리를 표시한다.
            // (dist[][] == 0이면 방문 안한 곳)
            dist = new int[N][N];
            minX = -1;
            minY = -1;
            minDist = Integer.MAX_VALUE;

            bfs(sharkX, sharkY);

            // 상어 사이즈와 물고기를 먹은 횟수를 비교해 같으면 -> 상어 사이즈++

            if (minX >=0 && minY >=0) {
            
                // 물고기가 먹힌 경우에는 물고기 좌표의 값을 0으로 바꿔주고
                // 상어 좌표의 값을 기존의 물고기 좌표값으로 바꿔줌
                // 그리고 해당 칸에 담긴 거리값을 총 거리에 추가
                
                eat++;
                maps[minX][minY] = 0;
                sharkX = minX;
                sharkY = minY;
                cnt += dist[minX][minY];

                if (eat == sharkSize) {
                    sharkSize++;
                    eat = 0;
                }
            }else break;
        }
        System.out.println(cnt);
    }

    static void bfs(int x, int y) {

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

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

                // 상어가 움직일 수 있는 칸인지, 방문 안한 곳인지 확인
                if (isInArea(nx, ny) && isAbleToMove(nx, ny) && dist[nx][ny] == 0) {
                    dist[nx][ny] = dist[cur.x][cur.y] + 1;

                    // 해당 칸에 먹을 수 있는 물고기가 존재하는 경우
                    // 최소값에 대한 정보 저장
                    
                    if (maps[nx][ny]!= 0 && maps[nx][ny]<sharkSize) {
                        if (minDist > dist[nx][ny]) {
                            minDist = dist[nx][ny];
                            minX = nx;
                            minY = ny;
                        } else if (minDist == dist[nx][ny]) {
                        
                            // 가장 거리가 짧은 물고기가 여러 마리인 경우
                            // 위부터, 그것도 같으면 왼쪽부터
                            
                            if (minX == nx) {
                                if (minY > ny) {
                                    minY = ny;
                                }
                            } else if (minX > nx) {
                                minX = nx;
                                minY = ny;
                            }
                        }
                    }
                    queue.add(new Node(nx, ny));
                }
            }
        }

    }

	// 해당 좌표가 maps의 범위 내에 존재하는지
    static boolean isInArea(int x, int y) {
        return (x<N && x>=0 && y<N && y>=0);
    }
	
    // 해당 칸을 상어가 지나쳐갈 수 있는지 (상어 사이즈보다 작거나 같은 값이어야함)
    static boolean isAbleToMove(int x,int y){
        return maps[x][y] <= sharkSize;
    }
}

*참고 - 풀이를 쓸거면 이렇게 써야하는데..라고 생각이 들 정도로 자세하게 설명해두셨다

profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글