tmddjs210   4년 전

반례나 지적좀 해주시면 감사하겠습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    private static int[][] <i>map</i>;
    private static int[] <i>dx </i>= {-1, 0, 1, 0};
    private static int[] <i>dy </i>= {0, -1, 0, 1};
    private static Queue<Point> <i>queue </i>= new LinkedList<>();
    private static TreeSet<Integer> <i>resultTreeSet </i>= new TreeSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.<i>in</i>);
        int N = sc.nextInt(); // 열(2차원) 6
        int M = sc.nextInt(); // 행(1차원) 4

        <i>map </i>= new int[M + 2][N + 2];

        //맵 세팅
        for (int i = 1; i < M + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                <i>map</i>[i][j] = sc.nextInt();
                if (<i>map</i>[i][j] == 1) {
                    <i>queue</i>.offer(new Point(i, j));
                }
            }
        }

        //바깥쪽 멥은 -1로 세팅 (사방히막힌 경우 구하기위해)
        for (int i = 0; i < N + 2; i++) {
            <i>map</i>[0][i] = -1;
            <i>map</i>[M + 1][i] = -1;
        }
        for (int i = 0; i < M + 2; i++) {
            <i>map</i>[i][0] = -1;
            <i>map</i>[i][N + 1] = -1;
        }

        //순차적 탐색
        <i>bfs</i>();

        //결과
        boolean isBlocked = false;
        for (int i = 1; i < M + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                if (<i>map</i>[i][j] >= 0) { //(예제입력 4 예외처리)
                    //사방막힌 곳 있는 경우
                    if (<i>map</i>[i - 1][j] < 0 && <i>map</i>[i + 1][j] < 0 && <i>map</i>[i][j - 1] < 0 && <i>map</i>[i][j + 1] < 0) {
                        //map 실제크기 범위벗어난 경우 (예제입력 5 예외처리)
                        if (i - 1 < 0 || j - 1 < 0 || i + 1 >= N || j + 1 >= M) {
                            continue;
                        }
                        System.<i>out</i>.println(-1);
                        isBlocked = true;
                        break;
                    }
                }
            }
            if (isBlocked) {
                break;
            }
        }
        if (!isBlocked) {
            if (<i>resultTreeSet</i>.isEmpty()) {
                System.<i>out</i>.println(0);
            } else {
                System.<i>out</i>.println(<i>resultTreeSet</i>.last() - 1);
            }
        }

    }


    private static void bfs() {
        while (!<i>queue</i>.isEmpty()) {
            Point point = <i>queue</i>.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + <i>dx</i>[i];
                int y2 = point.y + <i>dy</i>[i];

                if (<i>map</i>[x2][y2] == 0) {
                    <i>queue</i>.offer(new Point(x2, y2));
                    if (i == 0) { //왼쪽으로 이동한 상태
                        <i>map</i>[x2][y2] = <i>map</i>[x2 + 1][y2] + 1;
                    } else if (i == 1) {//상단으로 이동한 상태
                        <i>map</i>[x2][y2] = <i>map</i>[x2][y2 + 1] + 1;
                    } else if (i == 2) {//오른쪽으로 이동한 상태
                        <i>map</i>[x2][y2] = <i>map</i>[x2 - 1][y2] + 1;
                    } else {//밑으로 이동한 상태
                        <i>map</i>[x2][y2] = <i>map</i>[x2][y2 - 1] + 1;
                    }
                    <i>resultTreeSet</i>.add(<i>map</i>[x2][y2]);
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

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

tmddjs210   4년 전

해결했습니다. 생각나서 지금적네요

댓글을 작성하려면 로그인해야 합니다.