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

11월 10일(금) - 그래프와 순회 (2206번)

2206번: 벽 부수고 이동하기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(풀이출처 -> https://superohinsung.tistory.com/167 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static int N,M;
    public static int[][] arr;
    public static int[][] dist;
    public static boolean[][][] visited;
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};

    public static int result = -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());
        arr = new int[N][M];
        dist = new int[N][M];
        visited = new boolean[2][N][M];

        if(N-1 == 0 && M-1 == 0)
        {
            System.out.print(1);
            System.exit(0);
        }

        for(int i=0; i<N; i++)
        {
            String str = br.readLine();
            for(int j=0; j<M; j++)
            {
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        BFS();
        System.out.println(result);
    }

    private static void BFS(){
        LinkedList<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        arr[0][0] = -1;

        while (!queue.isEmpty())
        {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            int z = poll[2];

            for(int i=0; i<4; i++)
            {
                int next_X = x + dx[i];
                int next_y = y + dy[i];

                if(next_X<0 || next_y<0 || next_X>=N || next_y>=M)
                {
                    continue;
                }

                if(arr[next_X][next_y] == 1)
                {
                    if(z==0 && !visited[1][next_X][next_y])
                    {
                        visited[z][next_X][next_y] = true;
                        dist[next_X][next_y] = dist[x][y] + 1;
                        queue.offer(new int[]{next_X, next_y, 1});
                    }
                }

                else
                {
                    if(!visited[z][next_X][next_y])
                    {
                        visited[z][next_X][next_y] = true;
                        dist[next_X][next_y] = dist[x][y] + 1;
                        queue.offer(new int[]{next_X, next_y, z});
                    }
                }

                if(next_X == N-1 && next_y == M-1)
                {
                    result = dist[next_X][next_y] + 1;
                    return;
                }
            }
        }
    }
    
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ