알고리즘/문제풀이

[BFS] 미로탐색

lipnus 2018. 9. 10. 20:36
반응형

2178. 미로 탐색 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB3835212107754830.979%

문제

N×M크기의 배열로 표현되는 미로가 있다.

101111
101010
101011
111011

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 

4 6
101111
101010
101011
111011

예제 출력 1 

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

예제 입력 3 

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 

38

예제 입력 4 

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 

13




1. 위치를 클래스로 처리

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static int N, M;

    //for돌리기 편하게 상하좌우 변화량을 미리 저장해준다
    static Position[] dP = new Position[5];

    static boolean[][] visited;


    public static void main(String[] args) {
   // write your code here

        //상하좌우 변화량
        dP[1] = new Position(-1, 0);
        dP[2] = new Position(1, 0);
        dP[3] = new Position(0, -1);
        dP[4] = new Position(0, 1);


        N = sc.nextInt();
        M = sc.nextInt();
        int[][] maze = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];


        for(int i=1; i<=N; i++){
            String line = sc.next();

            for(int j=1; j<=M; j++){
                maze[i][j] = Integer.parseInt( line.substring(j-1,j) );
            }
        }


        System.out.println( bfs(maze) );

    }

    static int bfs(int[][] maze){

        Queue<Position> queue = new LinkedList<>();

        Position startPoint = new Position(1,1);
        visited[startPoint.N][startPoint.M] = true;
        queue.add(startPoint);

        Position P; //탐색위치
        int depth=1; //몇칸 떨어져있는지(간 거리가 아니라)

        while( !queue.isEmpty() ){ //큐가 빌때까지 돈다

            int qSize = queue.size();
            for(int i=1; i<=qSize; i++){
                P = queue.poll();


                //인접영역을 검사(상,하,좌,우)
                for(int j=1; j<=4; j++){

                    Position nP = new Position(P.N, P.M);
                    nP.sum( dP[j] ); //nextP에 변화량을 적용

                    //적용된 변화량 값이 이동가능한 곳인지 확인
                    if( 1<=nP.M && nP.M<=M && 1<=nP.N && nP.N<=N ){ //미로 밖으로 벗어났는지
                        if( visited[nP.N][nP.M]==false && maze[nP.N][nP.M]==1 ){ //이미 방문한 곳인지, 벽이 아니라 바닥인지

                            if(nP.N==N && nP.M==M){
                                depth++;
                                return depth;
                            }

                            visited[nP.N][nP.M] = true;
                            queue.add( nP );

                        }
                    }//if
                }//for(j)
            }//for(i)

            depth++; //한턴 끝
        }

        return -1;
    }


    //위치값을 저장하는 클래스
    static class Position{
        int N;
        int M;

        Position(int n, int m){
            N = n;
            M = m;
        }

        void sum(Position dP){
            M = M + dP.M;
            N = N + dP.N;
        }

    }
}










- 객체 만들어서 했는데, 배열 두개랑 큐 두개 동시에 써서 한 사람도 있었음.







2. 위치를 배열로 처리

package com.company;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Maze{

    static Scanner sc = new Scanner(System.in);
    static int N, M;
    static boolean[][] visited;

    //상하좌우
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};

    public static void main(String[] args) {

        N = sc.nextInt();
        M = sc.nextInt();
        int[][] maze = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];


        for(int i=1; i<=N; i++){
            String line = sc.next();

            for(int j=1; j<=M; j++){
                maze[i][j] = Integer.parseInt( line.substring(j-1,j) );
            }
        }


        System.out.println( bfs(maze) );

    }

    static int bfs(int[][] maze){

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

        int[] P = {1,1}; //현재위치(N,M)

        visited[1][1] = true;
        queue.add( P );

        int depth=1; //몇칸이동한 칸


        while( !queue.isEmpty() ){ //큐가 빌때까지 돈다

            int qSize = queue.size();
            for(int i=1; i<=qSize; i++){
                P = queue.poll();

                //인접영역을 검사(상,하,좌,우)
                for(int j=0; j<4; j++){

                    int[] nP = new int[2];
                    nP[0] = P[0]+ dy[j];
                    nP[1] = P[1]+ dx[j];

                    //적용된 변화량 값이 이동가능한 곳인지 확인
                    if( 1<=nP[0] && nP[0]<=N && 1<=nP[1] && nP[1]<=M ){ //미로 밖으로 벗어났는지
                        if( visited[ nP[0] ][ nP[1] ]==false && maze[ nP[0] ][ nP[1] ]==1 ){ //이미 방문한 곳인지, 벽이 아니라 바닥인지


                            if(nP[0]==N && nP[1]==M){
                                depth++;
                                return depth;
                            }

                            visited[nP[0]][nP[1]] = true;
                            queue.add( nP );
                        }
                    }//if
                }//for(j)
            }//for(i)

            depth++; //한턴 끝
        }

        return -1;
    }



}



큐에 배열넣을때 주솟값을 넣음.

int[] nP = new int[2];

반복문 돌때마다 매번 이렇게 생성하지 않고 반복문 밖에 선언해놓으면 큐에 들어간 값이 바뀌게 된다.

반응형