[알고리즘] 백준 2206 벽 부수고 이동하기 -dfs, bfs- 자바 코틀린

 

 

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

백준 dfs,bfs 단계별 풀이의 마지막 문제를 풀어봤습니다. ㅎㅎ

풀다가 모르겠어서 밑에 분의 풀이를 참고해서 풀었습니다.

velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%802206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-java

[Algorithm] 백준_2206 벽 부수고 이동하기 java

 

먼저 가중치가없는 최단거리이므로 BFS 로 풀어야합니다.

 

1. isVisited[][][] 방문여부는 기존 dfs, bfs 문제와 다르게 3차원 배열로 하여 벽을 부수고 방문한 곳인지 구분을 해줍니다. 0인 경우는 안부심, 1인경우는 부심으로 구분했습니다.

 

2. Point 클래스를 만들어 좌표와 부순 벽개수, 이동한 거리를 나타냅니다.

+)지인의 말씀에 따르면 여기서는 벽을 한번만 부술지 있지만 여러개 부실수 있는 문제 등 여러 응용문제가 있다고 합니다.

 

3. BFS 로 탐색을 하며 

1차로 벽인 경우와 벽이 아닌 경우 나누고

2차로 벽인 경우 -> 벽 부순적이 없고 벽부순후 방문한 적이 없던 경우에 탐색

     벽 아닌 경우 혹은 외부값인 경우(전 배열크기를 +2해서 하기때문에) ->   해당 벽을 방문한 적이 없던 경우에 탐색(이때 주의할 점은 방문배열의 3차원에 부순벽의 개수로 해줘야합니다.)

 

 

다음은 코드입니다.

 

[Java]

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

public class Main {

    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};
    private static int N; //수빈이 위치
    private static int M; //동생 위치
    private static int[][] map;
    private static boolean[][][] isVisited; //x,y, (0:안부심,1:부심)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N + 2][M + 2];
        isVisited = new boolean[N + 2][M + 2][2];
        for (int i = 1; i <= N; i++) {
            String line = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j + 1] = line.charAt(j) - '0';
            }
        }
        //바깥쪽 멥은 -1로 세팅 (사방히막힌 경우 구하기위해)
        for (int i = 0; i < M + 2; i++) { //왼쪽,오른쪽벽
            map[0][i] = -1;
            map[N + 1][i] = -1;
        }
        for (int i = 0; i < N + 2; i++) {
            map[i][0] = -1;
            map[i][M + 1] = -1;
        }
        bfs(1, 1);
    }

    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        //초깃값도 이동경로개수 포함
        queue.offer(new Point(x, y, 0, 1));
        isVisited[x][y][0] = true;
        isVisited[x][y][1] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            if (point.x == N && point.y == M) {
                System.out.println(point.distance);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                int destroyCnt = point.destroyCnt;
                int distance = point.distance;
                if (map[x2][y2] == 1) { //이동할 곳이 벽인 경우
                    if (destroyCnt == 0 && !isVisited[x2][y2][1]) { //벽부순적이없고 방문한적이 없던 곳
                        isVisited[x2][y2][1] = true;
                        queue.offer(new Point(x2, y2, destroyCnt + 1, distance + 1));
                    }
                } else if (map[x2][y2] != -1) { // 이동할 곳이 벽이 아닌 경우( + 쓰레기외부값아닌경우)
                    if (!isVisited[x2][y2][destroyCnt]) { //해당 벽을 방문하지 않은 경우
                        isVisited[x2][y2][destroyCnt] = true;
                        queue.offer(new Point(x2, y2, point.destroyCnt, distance + 1));
                    }
                }
            }
        }
        System.out.println(-1);
    }

    static class Point {
        int x;
        int y;
        int destroyCnt; //부순 벽개수
        int distance; // 이동한 거리

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


}

 

 

 

[Kotlin]

import java.util.*

private val dx = intArrayOf(0, 0, -1, 1)
private val dy = intArrayOf(-1, 1, 0, 0)
private var N: Int = 0 //수빈이 위치
private var M: Int = 0 //동생 위치
private var map: Array<IntArray>? = null
private var isVisited: Array<Array<BooleanArray>>? = null //x,y, (0:안부심,1:부심)


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    map = Array(N + 2) { IntArray(M + 2) }
    isVisited = Array(N + 2) { Array(M + 2) { BooleanArray(2) } }
    for (i in 1..N) {
        val line = sc.next()
        for (j in 0 until M) {
            map!![i][j + 1] = line[j] - '0'
        }
    }
    //바깥쪽 멥은 -1로 세팅 (사방히막힌 경우 구하기위해)
    for (i in 0 until M + 2) { //왼쪽,오른쪽벽
        map!![0][i] = -1
        map!![N + 1][i] = -1
    }
    for (i in 0 until N + 2) {
        map!![i][0] = -1
        map!![i][M + 1] = -1
    }
    bfs(1, 1)
}

private fun bfs(x: Int, y: Int) {
    val queue = LinkedList<Point>()
    //초깃값도 이동경로개수 포함
    queue.offer(Point(x, y, 0, 1))
    isVisited!![x][y][0] = true
    isVisited!![x][y][1] = true

    while (!queue.isEmpty()) {
        val point = queue.poll()
        if (point.x == N && point.y == M) {
            println(point.distance)
            return
        }
        for (i in 0..3) {
            val x2 = point.x + dx[i]
            val y2 = point.y + dy[i]
            val destroyCnt = point.destroyCnt
            val distance = point.distance
            if (map!![x2][y2] == 1) { //이동할 곳이 벽인 경우
                if (point.destroyCnt == 0 && !isVisited!![x2][y2][1]) { //벽부순적이없고 방문한적이 없던 곳
                    isVisited!![x2][y2][1] = true
                    queue.offer(Point(x2, y2, destroyCnt + 1, distance + 1))
                }
            } else if (map!![x2][y2] != -1) { // 이동할 곳이 벽이 아닌 경우( + 쓰레기외부값아닌경우)
                if (!isVisited!![x2][y2][destroyCnt]) {
                    isVisited!![x2][y2][destroyCnt] = true
                    queue.offer(Point(x2, y2, point.destroyCnt, distance + 1))
                }
            }
        }
    }
    println(-1)
}

data class Point(var x: Int, var y: Int, var destroyCnt: Int //부순 벽개수
            , var distance: Int // 이동한 개수
)

 

 

 

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%202206%20%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0

mtjin/algorithm_practice

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