BOJ) 벽 부수고 이동하기

벽 부수고 이동하기

2206번: 벽 부수고 이동하기

풀이

 

BFS 문제로, (1,1)에서 시작해서 (n,m)에 최소 경로로 도달하기 위해 몇 개의 칸을 밟는지 구하는 문제다.

처음에는 단순하게 visit을 좌표만 체크하면서 (2차원 배열) 답을 구해줬다.

50퍼센트 쯤 넘어갈 때 틀렸다고 뜨는 것을 보고, 벽을 허물고 이동한 경우와 벽을 허물지 않고 이동한 경우가 물린다는 것을 알아챘다.

 

그래서 visit 변수를 3차원 배열로 생성해주었는데, 벽을 한 번 허물었을 경우 이동 기록과 허물지 않고 이동한 이동 기록을 나눠주기 위해서였다.   boolean[][][] visit = new boolean [n][m][2];

 

처음 시작 위치를 넣을 때, step에 1, remain에 1을 넣어주었다.

처음 시작하는 칸도 총 밟게되는 칸에 포함되기 때문에 step 은 1이 된다.

처음 시작할 때는 벽을 허물지 않았으므로 remain은 1이 된다. ( 만약 벽을 세번 네번 허물 수있다면 remain은 그에따라 변한다. visit도)

 

나머지는 일반적으로 BFS를 통해 맵을 탐색하는 것과 같다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private final static char MOVE = '0', WALL = '1';
    private final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};

    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());

        char[][] map = new char[n][m];
        for(int i=0; i<n; i++) {
            map[i] = br.readLine().toCharArray();
        }
        br.close();

        solution(n,m,map);
    }

    private static void solution(int n, int m, char[][] map) {
        int answer =-1;
        LinkedList<Pos> moveList = new LinkedList<>();
        boolean[][][] visit = new boolean[n][m][2]; // 벽을 한 번 부순 경우와 부수지 않은 경우
        visit[0][0][1] = true; // 부수지 않은 채 이동
        moveList.offer(new Pos(0,0, 1,NO_BREAK));

        while(!moveList.isEmpty()) {
            Pos pos = moveList.poll();
            if(pos.x == m-1 && pos.y == n-1) {
                answer = pos.step;
                break;
            }
            int step = pos.step+1;
            int remain = pos.remain;

            for(int i=0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if(isInArea(nx,ny,m,n)) { // out of idx 방지
                    if(!visit[ny][nx][remain]) { // visit check
                        if (map[ny][nx] == MOVE) {
                            moveList.offer(new Pos(nx,ny,step, remain));
                            visit[ny][nx][remain] = true;
                        } else { // 벽의 경우
                            if (remain == NO_BREAK) { // 벽을 한번도 안부쉈다면
                                moveList.offer(new Pos(nx,ny,step, BREAK));
                                visit[ny][nx][BREAK] = true;
                            }
                        }

                    }
                }
            }
        }
        System.out.println(answer);
    }

    private static boolean isInArea(int x, int y, int m, int n) {
        return x>=0 && y>=0 && x<m && y<n;
    }

    private static class Pos {
        int x,y,step,remain;
        public Pos(int x, int y, int step, int remain) {
            this.x =x;
            this.y =y;
            this.step = step;
            this.remain =remain;
        }
    }
}