BOJ_2178 미로탐색 [Java] (S1)

문제 설명

풀이

미로탐색하는 것은 뭐다? 대부분 BFS로 모든 길을 탐색해봐야한다. 가끔 DFS나 백트래킹이 있지만 대부분 BFS로 먼저 해보는게 경험상 좋은 것 같다. BFS로 방향을 정하면 큰 문제가 없다.

 

매번 문제 풀듯이, queue에 넣어주고 visit체크해주고, 옮기면서 타당성 체크해주고 통과하면 다시 queue에 넣어준다. 결국 BFS, DFS 판별하는게 키포인트!!

 

DFS로도 해봤는데 시간 초과가 뜸!! 문제별로 속도차이가 꽤 있는 듯

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

    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());
        count = 0;
        map = new int[N+1][M+1];
        dis = new int[N+1][M+1];

        Queue<int[]> que = new LinkedList<int[]>();

        for(int i =0; i< N; i++){
            String[] input = br.readLine().split("");
            for(int j =0; j<M; j++){
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
//        for(int i =0; i< N; i++){
//            for(int j =0; j<M; j++){
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
        que.add(new int[] {0,0,0});
        dis[0][0] = 2;

        while (!que.isEmpty()) {
            int[] now =  que.poll();
            int x = now[0];
            int y = now[1];
            int cnt = now[2];
//            System.out.println("x축:"+y+" y축:"+x+" cnt:"+cnt);

            for(int z=0; z<4; z++){
                int cx = x + dx[z];
                int cy = y + dy[z];

                if(cx < 0 || cy < 0 || cx >= N || cy >= M || map[cx][cy] == 0 || dis[cx][cy] != 0){
                    continue;
                }
//                System.out.println("cx축:"+cy+" cy축:"+cx+" map:"+map[cx][cy]+" dis:"+dis[cx][cy]);
                dis[cx][cy] = 2;
                if (cx == N-1 && cy == M-1){
                    count = cnt+2;
                }
                que.add(new int[] {cx,cy,cnt+1});
            }
        }

        System.out.println(count);

    }
}

 

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

2178번: 미로 탐색