미로탐색(2178)

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

예제 입력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

풀이

일단 bfs이란 무엇인가에 대해서 이론적으로 확인해보았다.

기본 문제같은 경우이기 때문에 암기가 가장 좋을 것 같다고 생각되어서 이해가 되는대로 문제를 참고해서 풀어보았다.

import java.util.*;
import java.io.*;
public class Main{
    static int[][] arr;
    static int n, m;
    static boolean[][] visited;

    public static void main(String[] args) throws Exception{
        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];
        visited = new boolean[n][m];
        visited[0][0] = true;

        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(0,0);
        System.out.println(arr[n-1][m-1]);
    }

    public static void bfs(int x, int y){
        Queue<int[]> q = new LinkedList<int[]>();
        //현재 좌표를 넣어주고
        q.add(new int[] {x, y});
        //이동할 수 있는 가지 수, 동서남북
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        while(!q.isEmpty()){
            int[] xy = q.poll();

            for(int i=0; i<4; i++){
                //동서남북으로 탐색
                int nextX = xy[0] + dx[i];
                int nextY = xy[1] + dy[i];

                //만약 다음으로 넘어가는 곳이 미로를 벗어나거나
                //이미 탐색했던 곳이거나 벽이라면 다음 반복문으로 넘어가고
                if(nextX<0 || nextX>=n || nextY<0 || nextY>=m
                        || visited[nextX][nextY] || arr[nextX][nextY]==0)
                    continue;

                //다음 탐색 지점을 큐에 넣고
                q.add(new int[] {nextX, nextY});
                //탐색했다고 기록을 찍어두고
                visited[nextX][nextY] = true;
                //다음 탐색 지점에 현재 탐색지점+1해서 넣어주자
                arr[nextX][nextY] = arr[xy[0]][xy[1]]+1;
            }
        }
    }
}

클ㅡ

//클래스를 만들어서 문제를 해결하는 방법도 괜찮은 방법이라고 생각해서 다시 복습겸 연습중이다.
import java.util.*;
import java.io.*;
public class Main{
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    public static class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args)throws Exception{
        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];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++){
            String t = br.readLine();
            for(int j=0; j<m; j++){
                arr[i][j] = t.charAt(j)-'0';
            }
        }

        fn(new Point(0,0));
        System.out.println(arr[n-1][m-1]);
    }

    public static void fn(Point point){
        Queue<Point> q = new LinkedList<>();
        q.add(point);
        visited[point.x][point.y] = true;

        while(!q.isEmpty()){
            Point tmp = q.poll();
            for(int i=0; i<4; i++){
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=m || visited[nx][ny] || arr[nx][ny]!=1)
                    continue;
                q.add(new Point(nx, ny));
                visited[nx][ny] = true;
                arr[nx][ny] = arr[tmp.x][tmp.y]+1;
            }
        }
    }
}