BOJ 14497 주난의 난(JAVA) 🍫

문제 링크

14497번: 주난의 난(難)

문제 설명

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다.

문제 설명이 꽤 길어서 간략하게 보면 0이면 계속해서 사방탐색 가능, 아니면 점프 필요

'#'을 만날 때까지 최소 점프의 수를 찾자

입력

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)
둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)
이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

구조화

패딩을 안주고 입력에서 -1해서 저장

0인 경우랑 아닌 경우랑 분리해서 값(cnt) 저장

'#'을 만났을 때 정지, 값 출력

오답 노트

다익스트라문제는 꼭 PriorityQueue 쓰기!

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int n, m, sx, sy, ex, ey;
    public static char[][] map;
    public static boolean[][] v;
    public static int[][] way = {{0,1},{0,-1},{1,0},{-1,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());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken())-1;
        sy = Integer.parseInt(st.nextToken())-1;
        ex = Integer.parseInt(st.nextToken())-1;
        ey = Integer.parseInt(st.nextToken())-1;

        map = new char[n][m];
        v = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        bfs();
    }

    public static void bfs(){
        PriorityQueue<int[]> q = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
        q.offer(new int[] {sx, sy, 0});
        v[sx][sy] = true;

        while (!q.isEmpty()){
            int x = q.peek()[0];
            int y = q.peek()[1];
            int cnt = q.peek()[2];
            q.poll();
            if (x==ex && y==ey){
                System.out.println(cnt);
                return;
            }

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || v[nx][ny]) {
                    continue;
                }
                if (map[nx][ny]=='0'){
                    q.offer(new int[] {nx, ny, cnt});
                    v[nx][ny] = true;
                }
                else {
                    q.offer(new int[] {nx, ny, cnt+1});
                    v[nx][ny] = true;
                }
            }
        }
    }
}

git hub 링크