백준 14497번 주난의 난(難) Java

: ) YOUNG·2024년 2월 15일
1

알고리즘

목록 보기
318/417
post-thumbnail

백준 14497번
https://www.acmicpc.net/problem/14497

문제



생각하기




동작



결과


코드



import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, ans;
    private static Coordinate criminal, main;
    private static char[][] map;
    private static final int[] dirX = {-1, 1, 0, 0};
    private static final int[] dirY = {0, 0, -1, 1};

    private static class Coordinate {
        int x;
        int y;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } // End of Coordinate class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int count = 0;
        for (; ; ) {
            boolean ret = BFS();
            count++;

            if (ret) {
                break;
            }
        }

        sb.append(count);
        return sb.toString();
    } // End of solve()

    private static boolean BFS() {
        LinkedList<Coordinate> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[N + 1][M + 1];
        boolean flag = false;

        que.offer(main);
        isVisited[main.x][main.y] = true;


        while (!que.isEmpty()) {
            Coordinate current = que.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = dirX[i] + current.x;
                int nextY = dirY[i] + current.y;

                if (nextX == criminal.x && nextY == criminal.y) {
                    return true;
                }

                if (!isAbleCheck(nextX, nextY, isVisited)) continue;

                if (map[nextX][nextY] == '1') {
                    map[nextX][nextY] = '0';
                } else if (map[nextX][nextY] == '0') {
                    que.offer(new Coordinate(nextX, nextY));
                }

                isVisited[nextX][nextY] = true;
            }
        }

        return flag;
    } // End of BFS()

    private static boolean isAbleCheck(int nextX, int nextY, boolean[][] isVisited) {
        return nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= M && !isVisited[nextX][nextY];
    } // End of isAblecheck()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ans = 0;

        st = new StringTokenizer(br.readLine());
        main = new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        criminal = new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        map = new char[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String temp = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = temp.charAt(j - 1);
            }
        }
    } // End of input()
} // End of Main class

0개의 댓글