[백준] 2206번 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

# 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

# 입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

# 출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

# 예제 입력 1

6 4

0100

1110

1000

0000

0111

0000

# 예제 출력 1

15

# 예제 입력 2

4 4

0111

1111

1111

1110

# 예제 출력 2

-1

---

이 문제는 스스로의 힘으로 풀다가 도저히 안풀려서 다른 분들의 코드를 참조하면서 풀었다. 문제를 풀고 나니 내가 너무 복잡하게 생각했던 것은 아닌가 생각이 들고 코드를 올바를 뿐더러 이해하기 쉽고 명료하게 적는 것이 얼마나 어려운 것인지 다시 한번 깨닫게 되었다.

 

핵심은 BFS를 사용하는데, 각 정점마다 벽을 뚫었을 때의 값, 벽을 뚫지 않았을 때의 값을 나누어 구분해야 하는 점이다. 

 

BFS 메소드 내부에서 2가지 조건을 검사한다.

 

1) 현재 정점의 상하좌우 정점 중 벽이고 아직 벽을 부수지 않았다면,

-> 벽을 부수고 그 정점에 값을 대입 후 큐에 넣는다.

 

2) 현재 정점의 상하좌우 정점 중 길이고 아직 방문하지 않았다면,

-> 그 정점에 값을 대입 후 큐에 넣는다.

 

class Point{
	int y, x, wall;
}
int[m+2][n+2] graph;
/*
table의 [2]는 wall을 뜻함
벽을 부쉈다면 : 0
벽을 부수지 않았다면 : 1
*/
int[m+2][n+2][2] table;
Queue<Point> Q;

BFS(rows, cols)
{
	table[1][1][1] -> 1;
    Q.enqueue(Point(y, x, wall)
    
    while(!Q.isEmpty){
    	현재 정점 -> Q.dequeue
        
        if(현재 정점 == 목표 정점)
        	print(현재 정점의 값)
        
        현재 정점의 상하좌우 정점(next)에 대해:
    		if(next == 벽 & wall == 1)
            	next -> 현재 정점 + 1
                Q.enqueue(Point(next, wall - 1))
                
            else if(next == 길 & next 미방문)
            	next -> 현재 정점 + 1
                Q.enqueue(Point(next, wall))
                
     }
  print(-1)
}

# Whole Code </>

public class Main {

    static class Point{
        int y, x, wall;
        public Point(int y, int x, int wall){
            this.y=y;
            this.x=x;
            this.wall=wall;
        }
    }
    
    static int[] Y = {1,-1,0,0};
    static int[] X = {0,0,1,-1};
    static Queue<Point> Q = new LinkedList<>();
    static int[][] graph;
    static int[][][] table;

    static void BFS(int rows, int cols){

        //wall : 벽을 안부시면 1, 벽을 부시면 0
        table[1][1][1] = 1;
        Q.add(new Point(1,1,1));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int wall = p.wall;

            if(y == rows && x == cols){
                System.out.println(table[y][x][wall]);
                return;
            }

            for(int a=0; a<4; a++){
                int nextY = y + Y[a];
                int nextX = x + X[a];

                if( (nextX >= 0 && nextX <= cols) && (nextY >= 0 && nextY <= rows) )
                	//벽 & 벽 아직 안부심
                    if(graph[nextY][nextX] == 1 && wall == 1){ 
                        table[nextY][nextX][wall-1] = table[y][x][wall] + 1;
                        Q.add(new Point(nextY, nextX, wall-1));
                    }
                    //길 & 미방문
                    else if(graph[nextY][nextX] == 0 && table[nextY][nextX][wall] == 0){
                        table[nextY][nextX][wall] = table[y][x][wall] + 1;
                        Q.add(new Point(nextY, nextX, wall));
                    }
            }
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split(" ");
        int m = Integer.parseInt(str[0]); //rows
        int n = Integer.parseInt(str[1]); //cols

        graph = new int[m+2][n+2];
        table = new int[m+2][n+2][2];

        IntStream.rangeClosed(0, n+1).forEach(i->{
            graph[0][i]=1; graph[m+1][i]=1;
        });
        IntStream.rangeClosed(0, m+1).forEach(j->{
            graph[j][0]=1; graph[j][n+1]=1;
        });

        for(int i=1; i<=m; i++){
            str = br.readLine().split("");
            for(int j=1; j<=n; j++)
                graph[i][j] = Integer.parseInt(str[j-1]);
        }

        BFS(m,n);
    }
}

# References

jaimemin.tistory.com/650

백준 2206번 벽 부수고 이동하기