[BOJ-2206][시뮬레이션/BFS] 벽 부수고 이동하기 - Java

문제 바로가기

2206번: 벽 부수고 이동하기

 

어디서 어디까지의 최단 거리를 구하는 문제입니다. 최단 거리 구하는 문제는 웬만하면 BFS로 풀 수 있습니다.

다만 벽을 최대 한번 부수고 움직일 수 있기 때문에 한가지 더 고려해줘야 합니다.

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

public class Main{
    static String[] map;
    static int[][][] v;
    static int N, M;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    static class Dir{
        int y, x;
        boolean breaked;
        Dir(int y, int x, boolean breaked) {
            this.y = y; this.x = x; this.breaked = breaked;
        }
    }

    static boolean isIn(Dir c) {
        if(0 <= c.y && c.y < N && 0 <= c.x && c.x < M) return true;
        else return false;
    }

    public static int bfs() {
        Queue<Dir> q = new LinkedList<>();
        q.offer(new Dir(0, 0, false));

        v[0][0][0] = 1;
        while(!q.isEmpty()){
            Dir cur = q.poll();

            if(cur.y == N-1 && cur.x == M-1) {
                return cur.breaked == true ? v[cur.y][cur.x][1] : v[cur.y][cur.x][0];
            }

            for(int i = 0; i < 4; i++) {
                Dir next = new Dir(cur.y + dy[i], cur.x + dx[i], false);
                if(!isIn(next)) continue;

                if(cur.breaked == true) {                                // 벽 부순적 있을 때
                    if(v[next.y][next.x][1] != 0) continue;
                    if(map[next.y].charAt(next.x) == '0') {
                        v[next.y][next.x][1] = v[cur.y][cur.x][1] + 1;
                        next.breaked = true;
                        q.offer(next);
                    }
                }else {                                                    // 벽 부순적 없을 때
                    if(v[next.y][next.x][0] != 0) continue;
                    if(map[next.y].charAt(next.x) == '0') {
                        v[next.y][next.x][0] = v[cur.y][cur.x][0] + 1;
                        q.offer(next);
                    }else {
                        v[next.y][next.x][1] = v[cur.y][cur.x][0] + 1;
                        next.breaked = true;
                        q.offer(next);
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
        map = new String[N];
        v = new int[N][M][2];

        for(int i = 0; i < N; i++) map[i] = br.readLine();

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

방문 여부 함수를 3차원으로 만들어서 봐주면 됩니다.

v[y][x][1] 은 map[y][x]까지 벽 부수고 이동한 거리, v[y][x][0]은 벽 안 부수고 이동한 거리입니다.

 

그리고 Queue에도 좌표값만 넣는게 아니라 벽을 부수었는지 여부를 함께 넣어서 갖고 갈겁니다.

요 때 v 배열을 boolean 값을 갖도록 하고 Queue에 이동 거리를 넣어서 갖고 가도 됩니당.

 

BFS 돌면서 next를 볼때, 크게 이전에 벽을 부순적이 있는지 없는지로 구분해서 체크해줍니다.

벽을 부순 적이 있으면 이제 벽을 못 부수니깐 빈 칸으로만 움직일 수 있는거져.

 

벽을 부순 적이 없으면 벽을 부수면서 갈 수도 있고 빈 칸으로 갈 수도 있슴니다.

 

맨 처음 정답을 어떻게 리턴하나 고민이 있었슴니다.

안부수고 이동한게 거리가 더 적으면?? v[N-1][M-1][0] 이랑 [1] 중에서 최솟값을 구해서 리턴해야되나?? 

 

요것은 while() 문 안에서 체크하면 아무 필요 없슴니다. 왜냐면 최단거리기 때문에 먼저 들어온 친구가 무조건 거리가 짧기 떄문이져..

 

 

감사함니다...^^_