2206번

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

2206번: 벽 부수고 이동하기

오늘 풀어본 문제는 여지껏 해왔던 BFS문제와는 조금 다르다.

다른 문제들과 다른점이 무엇인가 하면 방문처리의 배열이 다르다.

지금까지는 1차원 또는 2차원 배열로 방문처리를 해왔다. 하지만 이 문제는 3차원 배열로 처리해야한다.(물론 토마토 문제의 경우 3차원이 있었다. 하지만 이 문제의 3차원 배열은 좀 다르다.)

 

문제의 내용은 벽을 딱 한번 부술 수 있고, (1,1)의 시작점에서 출발하여 (N,M)의 도착점으로 가는 최단경로를 구하는 것이다.

처음에는 큐에 넣는 조건만 신경을 썼었다. 하지만 답은 나오지 않았었다. 그래서 어떤 것이 문제인지 생각해 봤는데,

직접 그림을 그리고 해보는 과정에서 한번 벽을 뚫은 경로와 아직 벽을 뚫은 적이 없는 경로가 겹치는 위치가 있었다.

그 위치에서는 이미 방문처리가 되어 다른 한 경로가 막히는 경우가 발생했다.

그러면서 결과적으로 도달할 수 없게 된다.

그래서 벽을 뚫은 다음과 벽을 뚫지 않은 경로로 방문처리를 위한 배열을 나누었다.

 

그렇게하여 경로가 막히는 것을 막고 방문처리를 진행하여 내부 카운팅으로 경로를 계산하였다.

인접한 상하좌우를 탐색하면서 0이면 방문을 하고 아직 벽을 뚫지 않았다면 1을 방문하고 방문처리를 한다. 여기서 1이 방문처리되는 곳은 벽을 뚫은 횟수가 0인 경우이다.

 

아래의 코드가 방문처리의 조건문이다.

if(x>=0 && y>=0 && x<M && y<N && !visit[y][x][n.wall]){
    if(table[y][x]==0){
        queue.add(new node(x,y,n.cnt+1,n.wall));
        visit[y][x][n.wall]=true;
    }//벽 안뚫고 방문 가능
    else if(table[y][x]==1 && n.wall==0){
        queue.add(new node(x,y,n.cnt+1,1));
        visit[y][x][n.wall]=true;
    }//벽 뚫으면서 방문
   /* else if(table[y][x]==0 && n.wall==1){
        queue.add(new node(x,y,n.cnt+1,n.wall));
        visit[y][x][n.wall]=true;
    }//벽은 이미 뚫었고, 방문 가능한 곳*/
}

방문한 지점이 0이거나, 1이지만 아직 벽을 뚫지 않았거나로 나뉜다.

0인 경우는 벽과는 상관이 없기 때문에 큐에 넣을 때는 벽을 뚫었는지 여부는 그대로 한다.

1인 경우는 벽을 뚫는 것이기 때문에 이미 뚫은 경로는 뚫을 수 없고, 아직 벽을 뚫은 적이 없는 경로만 집어 넣기 때문에 벽을 뚫은 횟수를 1로 증가시킨다.

 

그래서 정답코드는 아래와 같다.

package backjoon.b2206;

import java.io.*;
import java.util.*;
public class b2206 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] table = new int[N][M];
        for(int i=0; i<N; i++){
            String tmp = br.readLine();
            for(int j=0; j<M; j++){
                table[i][j]= Integer.parseInt(String.valueOf(tmp.charAt(j)));
            }
        }
        Graph g = new Graph(table,N,M);
        System.out.println(g.bfs());
    }
}
class Graph{
    int N;
    int M;
    int[][] table;
    int[] dx={1,0,-1, 0};
    int[] dy={0,1, 0,-1};
    boolean[][][] visit;
    Queue<node> queue=new LinkedList<>();
    public Graph(int[][] table,int N,int M){
        this.table=table;
        this.N=N;
        this.M=M;
        visit=new boolean[N][M][2];
    }
    public int bfs(){
        queue.add(new node(0,0,1,0));
        visit[0][0][0]=true;
        visit[0][0][1]=true;//시작지점은 항상 방문하니까 방문처리
        while (!queue.isEmpty()){
            node n = queue.poll();
            if(n.x==M-1&&n.y==N-1&&n.wall<=1){
                return n.cnt;
            }
            for(int i=0; i<4; i++){
                int x = n.x+dx[i];
                int y = n.y+dy[i];
//벽을 한번 뚫은 경우 방문처리와, 벽을 아직 뚫지 않은 경우 방문처리를 따로해준다.
// 그 이유는 벽을 뚫은 다음 방문하는 것과 벽을 뚫지 않고 방문하는 경우가 겹치는 위치가 있어서다.
                if(x>=0 && y>=0 && x<M && y<N && !visit[y][x][n.wall]){
                    if(table[y][x]==0){
                        queue.add(new node(x,y,n.cnt+1,n.wall));
                        visit[y][x][n.wall]=true;
                    }//방문 가능
                    else if(table[y][x]==1 && n.wall==0){
                        queue.add(new node(x,y,n.cnt+1,1));
                        visit[y][x][n.wall]=true;
                    }//벽 뚫으면서 방문
                   /* else if(table[y][x]==0 && n.wall==1){
                        queue.add(new node(x,y,n.cnt+1,n.wall));
                        visit[y][x][n.wall]=true;
                    }//벽은 이미 뚫었고, 방문 가능한 곳*/
                }
            }
        }
        return -1;
    }
}
class node{
    int x;
    int y;
    int cnt;

    int wall;

    public node(int x, int y, int cnt, int wall) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.wall = wall;
    }
}