[알고리즘] 백준 2665 미로만들기 -BFS, 다익스트라, 최단경로- 자바

 

 

www.acmicpc.net/problem/2665

2665번: 미로만들기

 

 

 

 

백준 다익스트라 유형에서 한 문제를 골라 풀어봤는데 BFS에 가까운 문제였습니다.  ㅎㅎ

 

문제에 대해 간략히 설명하면, 

검은색방은 지나갈 수 없고 흰색방은 지나갈 수 있는데,

(0,0)에서 (N,N) 까지 가는데 최소한의 검은색-> 흰색 방으로 변경해야 하는 개수를 구하는 문제였습니다. 

 

 

해당 지점까지 오는데 색을 바꾼 값을 담는 배열인 distances 

- distances는 가장 큰 값(INF)로 초기화를 해줍니다.

방색깔을 담는 맵 배열인 map 

- 1: 흰색방, 0: 검은방

 

이 두 이차원 배열을 사용하여 BFS 탐색을 하게 됩니다.

탐색을 하되 해당 이동 좌표가 distances를 더 작은값으로 갱신한 경우에만 BFS 탐색을 진행하게 됩니다. 그리고 벽을 만난 경우 distances의 값은 1 증가하게 됩니다.

 

풀이는 다음과 같습니다.

 

[Java]

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

public class Main {
    private static int N;
    private static int[][] map; // 맵
    private static int[][] distances; // 해당 좌표까지 오는데 바꾼 방 색 개수
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};
    private static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        distances = new int[N][N];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < str.length(); j++) {
                map[i][j] = str.charAt(j) - '0';
                distances[i][j] = INF;
            }
        }
        System.out.println(bfs());
    }

    private static int bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0));
        distances[0][0] = 0;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int r = point.r;
            int c = point.c;
            for (int i = 0; i < 4; i++) {
                int r2 = r + dr[i];
                int c2 = c + dc[i];
                // 이동할 좌표 갱신 X , 더 작은값으로 갱신 가능한 경우
                if (r2 >= 0 && c2 >= 0 && r2 < N && c2 < N && (distances[r2][c2] > distances[r][c])) {
                    if (map[r2][c2] == 1) { // 이동가능경로
                        distances[r2][c2] = distances[r][c];
                        queue.add(new Point(r2, c2));
                    } else { // 벽
                        distances[r2][c2] = distances[r][c] + 1;
                        queue.add(new Point(r2, c2));
                    }
                }
            }
        }
        return distances[N - 1][N - 1];
    }

    static class Point {
        int r;
        int c;

        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!