[JAVA] 백준 14497 - 주난의 난(難)

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

주난이라는 애가 점프하면 상하좌우에서 출발한 파동을 처음으로 만난 친구(1)가 0으로 바뀌는데, 이때 #을 발견할때까지 필요한 점프의 횟수를 구하는 문제이다.

다익스트라 태그로 들어가서 문제를 풀었는데 BFS로 해도 편할 것 같아서 BFS로 풀었다.

점프 1회 당 주난이 위치에서 이동거리 1(친구를 만날 경우만 +1)로 만나는 애들을 0으로 바꾸고 continue해서 BFS while문을 탈출하도록 하고 count를 증가시킨 뒤 #을 만날때까지 이 과정을 반복했다.

 

char배열로 받아놓고 ==1로 비교를 하는 바람에 두번 틀렸다ㅡㅡ

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] size = getArray(br.readLine());
        int[] location = getArray(br.readLine());
        char[][] map = new char[size[0]][size[1]];
        for (int i = 0; i < map.length; i++) {
            map[i] = br.readLine().toCharArray();
        }
        map[location[0] - 1][location[1] - 1] = '*';
        map[location[2] - 1][location[3] - 1] = '#';

        Queue<Block> q = new LinkedList<>();
        int count = 1;
        while (true) {
            boolean[][] visited = new boolean[size[0]][size[1]];
            q.offer(new Block(location[0] - 1, location[1] - 1, 0));
            while (!q.isEmpty()) {
                Block poll = q.poll();
                int i = poll.i;
                int j = poll.j;
                int depth = poll.depth;
                if (visited[i][j]) continue;
                visited[i][j] = true;
                if (depth == 1 && map[i][j] == '1') {
                    map[i][j] = '0';
                    continue;
                }
                if (map[i][j] == '#') {
                    System.out.println(count);
                    return;
                }
                for (int k = 0; k < 4; k++) {
                    int ti = i + dx[k];
                    int tj = j + dy[k];
                    if (check(ti, tj, visited)) {
                        if (map[ti][tj] == '1' || map[ti][tj] == '#') {
                            q.offer(new Block(ti, tj, depth + 1));
                        } else {
                            q.offer(new Block(ti, tj, depth));
                        }
                    }
                }
            }
            count++;
        }

    }

    static boolean check(int i, int j, boolean[][] visited) {
        if (i < 0 || i >= visited.length) return false;
        if (j < 0 || j >= visited[0].length) return false;
        if (visited[i][j]) return false;
        return true;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Block {
    int i;
    int j;
    int depth = 0;

    Block(int i, int j, int depth) {
        this.i = i;
        this.j = j;
        this.depth = depth;
    }
}