[2178] 미로 탐색(BFS)

문제

---

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

 

입력

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

출력 

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

 

예시

4 6
101111
101010
101011
111011
//15

 

Key Point

---

• 상하좌우로 이동할 수 있는 좌표
• 배열 데이터를 저장할 객체
• 방문 여부를 체크할 객체

 

풀이

---

1. BFS를 이용하여 상하좌우를 탐색 
2. 이동 가능한 위치 큐에 저장 후 해당 위치 값 카운트++

 

 

풀이1

public class Maze {
    static int[][] board;   //데이터 저장할 보드
    static int n;   
    static int m;   
    static boolean[][] visited;    //방문 여부 체크
    static int[] dx = {-1, 1, 0, 0};    //x배열(상하)
    static int[] dy = {0, 0, 1, -1};    //y배열(좌우)

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

        board = new int[n][m];
        //한줄씩 열에 대한 입력값 받기
        for (int i = 0; i < n; i++) {   
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j) - '0';
            }
        }
        visited = new boolean[n][m];
        visited[0][0] = true;
        bfs(0,0);		//시작 위치 전달
        System.out.println(board[n-1][m-1]);
    }
    public static void bfs(int x,int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});		//큐에 현재 위치 저장

        while (!q.isEmpty()) {
            int[] now = q.poll();		//임시 배열에 현재 위치 꺼내서 저장
            int tx = now[0];		//x 대입
            int ty = now[1];    	//y 대입
            for (int i = 0; i < 4; i++) { 
            	//상하좌우 탐색
                int nx = tx + dx[i];
                int ny = ty + dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=m)     //보드 범위에서 벗어나면 다음 위치 탐색
                    continue;
                if(visited[nx][ny] || board[nx][ny] ==0 )  //방문한 적 있거나 보드가 0이면 다음 위치 탐색
                    continue;
                    
                //next actions
                q.add(new int[]{nx, ny});		//큐에 현재 위치 저장
                board[nx][ny] = board[tx][ty] + 1;		//보드 현재 위치에 카운트++
                visited[nx][ny] = true;		//현재 위치 방문 체크
            }
        }
    }
}

 

풀이2(좌표 클래스有)

class Point {
    static int x;
    static int y;
    public Point(int x,int y){
        this.x= x;
        this.y=y;
    }
}
public class MazeWithPoint {
    static int[][] board;   //데이터 저장할 보드
    static int n;   
    static int m;   
    static boolean[][] visited;    //방문 여부 체크
    static int[] dx = {-1, 1, 0, 0};    //x배열(상하)
    static int[] dy = {0, 0, 1, -1};    //y배열(좌우)

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

        board = new int[n][m];
        //한줄씩 열에 대한 입력값 받기
        for (int i = 0; i < n; i++) { 
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j) - '0';
            }
        }
        visited = new boolean[n][m];
        visited[0][0] = true;
        bfs(0,0);		//시작 위치 전달
        System.out.println(board[n-1][m-1]);
    }
    public static void bfs(int x,int y){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y));		//큐에 현재 위치를 담은 point 객체 저장
        while (!q.isEmpty()) {
            Point now = q.poll();		//point 객체에 임시로 현재 위치 저장
            for (int i = 0; i < 4; i++) {
            	//상하좌우 탐색
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=m)		//보드 범위에서 벗어나면 다음 위치 탐색
                    continue;
                if(visited[nx][ny] || board[nx][ny] ==0 )	//방문한 적 있거나 보드가 0이면 다음 위치 탐색
                    continue;
                    
                //next actions
                q.add(new Point(nx,ny));		//큐에 현재 위치 저장
                board[nx][ny] = board[now.x][now.y] + 1;		//보드 현재 위치에 카운트++
                visited[nx][ny] = true;     //현재 위치 방문 체크
            }
        }
    }