[알고리즘]백준 2206: 벽 부수고 이동하기

 

해결방법

최단 경로이므로 BFS로 접근한다.

단, 이동하는 도중에 한개의 벽을 부수고 이동할 수 있다는 변수가 있다. 벽의 위치를 저장하고 먼저 벽을 부수고 출발하면 최악의 경우 시간복잡도가 O((N*M)^2)로 시간초과가 발생한다.

따라서 3차원 배열로 거리/방문체크를 해야한다. 3차원 배열인 이유는 map 자체가 2차원 배열이고 벽을 부수지 않은 경우/벽을 부순경우를 나눠야 한다. 벽을 부수고 간 것이 먼저 도착하는 경우 벽을 부수지 않고 도착한 것이 방문처리되어 통과되지 못할 수 있기 때문이다.

 

코드1(거리 비교)

import java.util.*;
import java.io.*;

public class Main_2206_G3_벽부수고이동하기_거리체크 {
    static int N,M; // N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)
    static int[][] map;
    static int[][][] dp;
    static int[] dr = {-1,1,0,0}; //상하좌우
    static int[] dc = {0,0,-1,1};

    static class Point{
        int r,c;
        int dist;
        int isBreak; // 1: 이미 부심, 0: 아직 안부심
        public Point(int r, int c){
            this.r = r;
            this.c = c;
            this.dist = 0;
            this.isBreak = 0;
        }
        public Point(int r, int c, int dist, int isBreak){
            this.r = r;
            this.c = c;
            this.dist = dist;
            this.isBreak = isBreak;
        }
        @Override
        public String toString(){
            return "r="+r+",c="+c+", dist="+dist;
        }
    }

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        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 int[N+1][M+1];
        dp = new int[N+1][M+1][2];
        for(int i=1; i<=N; i++){
            String s = br.readLine();
            for(int j=1; j<=M; j++) {
                map[i][j] = s.charAt(j-1) - '0';
                Arrays.fill(dp[i][j],Integer.MAX_VALUE);
            }
        }

        // 2. BFS
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(1,1,1,0));
        while(!q.isEmpty()){
            Point cur = q.poll();
            int cr = cur.r;
            int cc = cur.c;
            int cd = cur.dist;
            int cb = cur.isBreak;
            if(dp[cr][cc][cb]<=cd) continue;
            dp[cr][cc][cb] = cd;

            if(cr==N && cc==M) break;

            for(int i=0; i<4; i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];
                if(nr<=0 || nr>N || nc<=0 || nc>M) continue;
                if(map[nr][nc]==0){
                    q.add(new Point(nr, nc, cd+1, cb));
                }
                if(map[nr][nc]==1 && cb==0){
                    q.add(new Point(nr, nc, cd+1, 1));
                }
            }
        }

        // 3. 출력
        int answer = Math.min(dp[N][M][0], dp[N][M][1]);
        if(answer==Integer.MAX_VALUE) answer = -1;
        System.out.println(answer);
    }
}

 

코드2(방문 체크)

import java.io.*;
import java.util.*;

public class Main_2206_G3_벽부수고이동하기_방문체크 {
    static int N,M; // N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)
    static int[][] map;
    static boolean[][][] visited;
    static int[] dr = {-1,1,0,0}; //상하좌우
    static int[] dc = {0,0,-1,1};

    static class Point{
        int r,c;
        int dist;
        int isBreak; // 1: 이미 부심, 0: 아직 안부심
        public Point(int r, int c){
            this.r = r;
            this.c = c;
            this.dist = 0;
            this.isBreak = 0;
        }
        public Point(int r, int c, int dist, int isBreak){
            this.r = r;
            this.c = c;
            this.dist = dist;
            this.isBreak = isBreak;
        }
        @Override
        public String toString(){
            return "r="+r+",c="+c+", dist="+dist;
        }
    }

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        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 int[N+1][M+1];
        visited = new boolean[N+1][M+1][2];
        for(int i=1; i<=N; i++){
            String s = br.readLine();
            for(int j=1; j<=M; j++) {
                map[i][j] = s.charAt(j-1) - '0';
                Arrays.fill(visited[i][j],false);
            }
        }

        // 2. BFS
        int answer = -1;
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(1,1,1,0));
        visited[1][1][0]=true;
        while(!q.isEmpty()){
            Point cur = q.poll();
            int cr = cur.r;
            int cc = cur.c;
            int cd = cur.dist;
            int cb = cur.isBreak;

            if(cr==N && cc==M) {
                answer = cd;
                break;
            }

            for(int i=0; i<4; i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];
                if(nr<=0 || nr>N || nc<=0 || nc>M) continue;
                if(map[nr][nc]==0 && !visited[nr][nc][cb]){
                    q.add(new Point(nr, nc, cd+1, cb));
                    visited[nr][nc][cb]=true;
                }
                if(map[nr][nc]==1 && cb==0 && !visited[nr][nc][1]){
                    q.add(new Point(nr, nc, cd+1, 1));
                    visited[nr][nc][1]=true;
                }
            }
        }

        // 3. 출력
        System.out.println(answer);
    }
}

 

링크

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