[Baekjoon] 2178번 미로 탐색

접근

• 편의를 위해 N+1, M+1 크기 만큼의 이중배열 사용
• 방문 여부 확인을 위한 visited 이중 배열 사용
• bfs 방식을 위한 count 이중 배열 사용(미로 이중배열과 같은)

 

---

 

해결

 

BFS

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

public class Main {

    static int N;
    static int M;
    static int[][] miro;
    static int[][] countMiro;
    static int[][] visited;
    static Integer result = null;
    static Queue<int[]> queue = new LinkedList<>();

    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());

        miro = new int[N+1][M+1];
        countMiro = new int[N+1][M+1];
        visited = new int[N+1][M+1];
        visited[1][1] = 1;

        for(int i=1;i<=N;i++){

            String[] elements = br.readLine().split("");

            for(int j=1;j<=M;j++){

                int element = Integer.parseInt(elements[j-1]);

                miro[i][j] = element;
                countMiro[i][j] = element;
            }
        }

        queue.add(new int[]{1, 1});

        bfs();

        System.out.println(result);
    }

    public static void bfs(){

        while(queue.isEmpty() == false){
            int[] current = queue.poll();
            int currentX = current[0];
            int currentY = current[1];

            if(currentX==M && currentY==N){
                result = countMiro[currentY][currentX];
                return;
            }

            if(0 < currentX-1 && miro[currentY][currentX-1] == 1 && visited[currentY][currentX-1] == 0){
                visited[currentY][currentX-1] = 1;
                countMiro[currentY][currentX-1] = countMiro[currentY][currentX]+1;
                queue.add(new int[]{currentX-1, currentY});
            }

            if(0 < currentY-1 && miro[currentY-1][currentX] == 1 && visited[currentY-1][currentX] == 0){
                visited[currentY-1][currentX] = 1;
                countMiro[currentY-1][currentX] = countMiro[currentY][currentX]+1;
                queue.add(new int[]{currentX, currentY-1});
            }

            if(currentX+1 <= M && miro[currentY][currentX+1] == 1 && visited[currentY][currentX+1] == 0){
                visited[currentY][currentX+1] = 1;
                countMiro[currentY][currentX+1] = countMiro[currentY][currentX]+1;
                queue.add(new int[]{currentX+1, currentY});
            }

            if(currentY+1 <= N && miro[currentY+1][currentX] == 1 && visited[currentY+1][currentX] == 0){
                visited[currentY+1][currentX] = 1;
                countMiro[currentY+1][currentX] = countMiro[currentY][currentX]+1;
                queue.add(new int[]{currentX, currentY+1});
            }
        }
    }
}

 

DFS(시간 초과)

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

public class Main {

    static int N;
    static int M;
    static int[][] miro;
    static Integer result = null;

    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());

        miro = new int[N+1][M+1];
        int[][] visited = new int[N+1][M+1];
        visited[1][1] = 1;

        for(int i=1;i<=N;i++){

            String[] elements = br.readLine().split("");

            for(int j=1;j<=M;j++){

                int element = Integer.parseInt(elements[j-1]);

                miro[i][j] = element;
            }
        }

        dfs(1, 1, visited, 1);

        System.out.println(result);
    }

    public static void dfs(int X, int Y, int[][] visited, int count){

        if(X==M && Y==N){
            if(result == null){
                result = count;
            }
            else{
                result = Math.min(result, count);
            }
            return;
        }

        if(0 < X-1 && miro[Y][X-1] == 1 && visited[Y][X-1] == 0){
            int[][] newVisited = copyVisited(visited);
            newVisited[Y][X-1]=1;
            recurse(X-1, Y, newVisited, count+1);
        }

        if(0 < Y-1 && miro[Y-1][X] == 1 && visited[Y-1][X] == 0){
            int[][] newVisited = copyVisited(visited);
            newVisited[Y-1][X]=1;
            recurse(X, Y-1, newVisited, count+1);
        }

        if(X+1 <= M && miro[Y][X+1] == 1 && visited[Y][X+1] == 0){
            int[][] newVisited = copyVisited(visited);
            newVisited[Y][X+1]=1;
            recurse(X+1, Y, newVisited, count+1);
        }

        if(Y+1 <= N && miro[Y+1][X] == 1 && visited[Y+1][X] == 0){
            int[][] newVisited = copyVisited(visited);
            newVisited[Y+1][X]=1;
            recurse(X, Y+1, newVisited, count+1);
        }
    }

	// 강복사를 통한 visited 물리적 분리, 편의 복사 메서드
    public static int[][] copyVisited(int[][] visited){
        int[][] copied = new int[N+1][M+1];

        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                copied[i][j] = visited[i][j];
            }
        }

        return copied;
    }

	// 현재 상황 조회를 위한 로깅 함수
    public static void printMiro(){
        String result = "";

        System.out.println();
        for(int i=0;i<=N;i++){
            for(int j=0;j<=M;j++){
                result += miro[i][j]+" ";
            }
            result += "\n";
        }

        System.out.println(result);
    }

	// 현재 상황 조회를 위한 로깅 함수
    public static void printVisited(int[][] visited){
        String result = "";

        System.out.println();
        for(int i=0;i<=N;i++){
            for(int j=0;j<=M;j++){
                result += visited[i][j]+" ";
            }
            result += "\n";
        }

        System.out.println(result);
    }
}