[백준 2206, Java] 벽부수고 이동하기

문제

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

풀이1 - 시간초과

- map 의 값을 입력 받을 때, 벽인 경우 그 좌표를 ArrayList에 add한다

- ArrayList를 순회하면서 index에 해당하는 벽의 좌표를 지나갈 수 있는 길(PATH)로 바꾼다

- bfs

- index에 해당하는 벽의 좌표를 다시 벽(WALL)로 바꾼다

 

이렇게 하면 시간복잡도는 NM^2으로 10의 12제곱이 된다. 시간초과가난다

 

풀이2 

 시간 초과를 줄이려면 한번 순회를 할 때 벽을 부술지 말지를 결정해야한다. 

 

현재위치에서 다음위치로 이동했을 때, 다음위치가 벽이라면 벽을 부수고 이동할 수 있는지 없는지의 여부는 (0,0)에서 현재위치까지 벽을 부순 횟수에 따라 달라진다. 만약 현재위치까지 벽을 부순 횟수가 0이 아니면 다음위치의 벽을 부수고 이동할 수 없다. 만약 현재위치까지 벽을 부순 횟수가 0이라고 하자. 그런데 다음 위치의 벽을 이전순회에서 방문한 적이 있다면 벽을 부수고 이동할 수 없다.

 

 따라서 방문처리의 배열은 visited[x][y][0 or 1]

 visited[x][y][0] = 벽을 부순적이 없는 노드가 방문했는지여부 , visited[x][y][1] = 벽을 부순적이 있는 노드가 방문했는지 여부

이런 식으로 구현해줘야 한다. ( 아직 이 부분이 완벽하게 이해되지는 않는다)

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point{
    int x, y, distance, breakCount;
    Point(int x, int y, int distance, int breakCount){
        this.x = x;
        this.y =y;
        this.distance =distance;
        this.breakCount = breakCount;
    }
}
public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][][] visited;
    public static final int PATH = 0;
    public static final int WALL = 1;
    public static final int NOT_BROKEN = 0;
    public static final int BROKEN = 1;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String[] line;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M][2];

        for(int r= 0; r<N; r++){
            line = br.readLine().split("");
            for(int c=0; c<M; c++){
                map[r][c] = Integer.parseInt(line[c]);
            }
        }

        int minDistance = bfs();
        bw.write(String.valueOf(minDistance));
        bw.flush();

    }
    public static int bfs(){
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0,1,0));
        visited[0][0][NOT_BROKEN] = true;

        while(!queue.isEmpty()){
            Point currentPoint = queue.poll();
            if(currentPoint.x ==N-1 && currentPoint.y ==M-1){
                return currentPoint.distance;
            }
            else{
                for(int d =0; d<4; d++){
                    int nx = currentPoint.x + dx[d];
                    int ny = currentPoint.y + dy[d];
                    int nd = currentPoint.distance +1;

                    if(nx>=0 && nx<N && ny>=0 && ny<M){
                        if(map[nx][ny] ==PATH){
                            if(!visited[nx][ny][currentPoint.breakCount]) {
                                visited[nx][ny][currentPoint.breakCount] = true;
                                queue.add(new Point(nx, ny, nd, currentPoint.breakCount));
                            }
                        }
                        else{
                            //벽인경우
                            if(currentPoint.breakCount==0){
                                if(!visited[nx][ny][BROKEN]){
                                    visited[nx][ny][BROKEN] =true;
                                    queue.add(new Point(nx,ny,nd, currentPoint.breakCount+1));
                                }
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

}