[Java] 다익스트라, BFS | 백준 2665 미로만들기

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

 

 

접근 방법 

 

이 문제는 다익스트라 알고리즘을 활용하여 풀 수 있다. 여기서는 각 방을 노드로 보고, 검은 방에서 흰 방으로 변경하는 작업을 가중치로 간주해 최소 변경 횟수 경로를 구한다. 최단 경로가 아닌 '최소 변경 횟수'를 찾는다는 점이 일반적인 다익스트라 알고리즘과의 차이다.

 

시작부터 끝방까지 가는 동안 검은 방(0)을 최소로 지나야 한다.

즉 흰 방(1)을 지나갈 때는 비용이 발생하지 않고 검은 방(0)을 거칠 때는 비용이 1 만큼 발생한다고 간주하고, 시작부터 끝방까지 BFS를 진행하여 최소 비용으로 끝방에 도착하는 경우를 구하면 된다.

 

우선순위 큐(PriorityQueue)를 사용해 현재 변경 횟수가 가장 적은 경로부터 탐색한다. 이를 위해 아래와 같이 현재 노드의 x,y 좌표와 변경 횟수를 속성을 가지는 Point 클래스를 정의한다.

static class Point implements Comparable<Point>{
    int x, y;
    int change;

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

    @Override
    public int compareTo(Point other){//change 작은 것 우선
        return Integer.compare(this.change, other.change);
    }
}

 

static int n;
static char[][] maze;
static int[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

 

visited 배열은 해당 지점의 최소 변경 횟수를 저장한다. 초기의 visited 배열은 최대값으로 설정해준다.

우선순위 큐에 시작 정점(new Point(0,0,0))을 담고 BFS 진행

 

상하좌우로 이동하며 change 값 계산 후 visited 배열을 업데이트 해준다.

• '1'인 칸으로 이동할 때는 비용이 들지 않음 (change + 0)
• '0'인 칸으로 이동할 때는 비용이 1 증가 (change + 1)

다음으로 change 값이 적은 정점으로 위 과정을 끝 지점 도달시 까지 반복한다.

private static int solution() {
    visited = new int[n][n];
    for(int i=0; i<n; i++){
        Arrays.fill(visited[i], Integer.MAX_VALUE);
    }

    PriorityQueue<Point> q = new PriorityQueue<>();
    q.offer(new Point(0,0,0));

    while(!q.isEmpty()){
        Point current = q.poll();
        int x = current.x;
        int y = current.y;

        if(x== n-1 && y == n-1){
            return current.change;
        }

        for(int i=0; i<4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX < 0 || nextX > n-1 || nextY < 0 || nextY > n-1) continue;

            int change = current.change + (maze[nextX][nextY] == '1' ? 0 : 1);

            if(change < visited[nextX][nextY]){
                visited[nextX][nextY] = change;
                q.offer(new Point(nextX, nextY, change));
            }
        }
    }

    return -1;
}

 

 

배운점 :

최단 경로를 찾아가는 다익스트라 알고리즘이 다양한 문제에 응용될 수 있음을 알게 되었다. 특히 이 문제는 그래프의 가중치를 경로가 아닌 새로운 기준(변경 횟수)으로 설정하는 것이 풀이의 핵심이였던 것 같다.