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

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

2206번: 벽 부수고 이동하기

 

 

---

 

처음 시도 때 시간 초과로 풀지 못한 문제다.

 

모든 벽을 큐에 넣고 해당 부분을 0으로 만들었다가 bfs가 종료되면 다시 1로 만드는 식으로

과정을 진행시켰는데 시간초과가 걸렸다.

 

 

생각을 해보면 BFS는 최단 경로를 찾을 수 있고,

Node class를 만들어서 BFS를 하면 해당 Node가 가장 먼저 도착한 Node일 테니 

벽을 뚫은적이 있는지, 없는지에 대한 상태를 저장시키면서 진행하면 될 것 같았다.

 

 

3차원 배열을 이용한 풀이가 있는데, 

3차원을 쓰지 않고, 방문처리 배열을 따로 사용하지 않고도

단순 2차원 graph로 로직 처리를 해주면 풀 수 있다.

 

 

	0	1	2	3
벽을 뚫은 적 x	O	O	O	X
벽을 뚫은 적 o	O	X	X	X

 

 

BFS 큐에 넣기 전 해당 위치의 값을 확인해서 사용가능성을 판단해주면 된다.

 

 

0

[ 방문하지 않은 상태 ]

 두 상태 다 사용 가능

해당 위치를 재방문 방지를 위해 2로 바꾼다.

 

 

1

[ 벽 ]

방문한 Node가 이미 벽을 뚫었다면 더 뚫을 수 없으므로 continue (더이상 뚫을 수 없음)

방문한 Node가 벽을 안뚫었다면 상태를 벽을 뚫은 상태로 바꾼다. 해당 위치는 다시 사용할 일이 없으므로 값을 3으로 바꾼다.

 

 

2

[ 벽을 뚫은 적 없는 Node를 위해 중간 방문 처리함 ]

방문한 Node가 벽을 뚫은 상태라면  continue (앞서 간 Node가 있음)

방문한 Node가 벽을 뚫지 않은 상태라면 해당 위치를 다신 사용하지 않도록 3으로 바꾼다.

 

 

3

[ 완전 방문된 상태 ]

해당 위치는 모든 노드가 사용할 수 없다.

(벽을 뚫지 않은 Node가 이미 지나간 상태)

 

 

 

 

벽을 뚫은 적이 없는 Node가 해당 위치를 완전 방문 처리하는 우선권이 있다고 생각하고, 최종 결정권을 준다.

방문한 Node의 상태를 확인하여 위치를 4가지 분기로 나눠서 해결해줄 수 있다.

 

 

---

 

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[][] graph;

    static Queue<Node> q = new LinkedList<>();
    static int low, col;
    static int[] xRange = {1, -1, 0, 0};
    static int[] yRange = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        low = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());

        graph = new int[low][col];

        for(int i = 0; i< graph.length; i++){
            String str = br.readLine();
            int idx = 0;
            for(int j =0; j< graph[i].length; j++){
                int ele = Integer.parseInt(str.charAt(idx) +"");
                graph[i][j] = ele;
                idx++;
            }
        }
        System.out.println(bfs());
    }

    //
    public static int bfs(){
        int dis = 1;
        q.add(new Node(0, 0, false, dis));
        graph[0][0] = 2;

        int[] xRange = {1, -1, 0, 0};
        int[] yRange = {0, 0, 1, -1};

        while(!q.isEmpty()){
            Node node = q.poll();
            dis = node.dis;
            if(node.x == graph.length - 1 && node.y == graph[0].length -1)
                return dis;

            for(int i = 0; i<4; i++){
                int x = xRange[i] + node.x;
                int y = yRange[i] + node.y;
                if(x>=0 && x<low && y>=0 && y<col){
                    int disn = node.dis + 1;

                    if(graph[x][y] == 3)
                        continue;

                    if(node.state){
                        if(graph[x][y] == 0) {
                            q.offer(new Node(x, y, node.state, disn));
                            graph[x][y] = 2;
                        }

                    }else{
                        if(graph[x][y] == 0 || graph[x][y] == 2){
                            q.offer(new Node(x, y, false, disn));
                            graph[x][y] = 3;
                        }

                        else if(graph[x][y] == 1){ // 벽을 뚫는다.
                            q.offer(new Node(x, y, true, disn));
                            graph[x][y] = 3;
                        }
                    }
                }
            }
        }
        return -1;
    }
}

class Node{
    int x;
    int y;
    boolean state;
    int dis;
    Node(int x, int y, boolean state, int dis){
        this.x = x;
        this.y = y;
        this.state = state;
        this.dis = dis;
    }
}