★백준/2178 미로탐색 /bfs

미로 탐색 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

192 MB

143947

62393

40055

42.067%

문제

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

---

풀이

dfs -> 실패

bfs -> 성공

 

 

 

시간초과 실패한 DFS

모든 경우를 탐색한후 이동한횟수가 최소값인지 체크하는 DFS는 느리다.

dfs에서 사용했던 

static int count;
하나의 분기를 진행하기전 진행시켜주고 분기가 끝나면 감소시켜주는게 그 분기가 끝났을때 분기를 시작하기전과 같은 상태를 만들어줘야하기 때문이다.
몇번 이동했는지를 저장하는 count변수는 static으로 선언하면 공용변수가 되므로 모든 경우를 살펴보려면 증가시키고 dfs불러오고,다시 감소시켜줘야한다.

static boolean[][] visited;
지금 이 탐색중에 어디를 방문했는지 저장하는 방문배열은 공유를 하게되면 하나의 탐색(하나의 경우의수)가 끝나고 다른탐색(다른 경우의수)가 시작될때 같은 방문배열을 사용하게 되므로 문제가생긴다.
    조합에서 해당 수를 뽑고, 안뽑고를 하면서 새로운 경우의수를 만들듯이. 방문처리하고, dfs실행하고, 방문처리를 취소해야한다.

static void dfs(int x,int y) throws IOException {
    if (x == n-1 && y == m-1) {
        min = Math.min(min, count);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
            if (!visited[nextX][nextY] && map[nextX][nextY] != 0) {
                visited[nextX][nextY] = true;
                count++;
                dfs(nextX, nextY);
                visited[nextX][nextY] = false;
                count--;
            }
        }
    }

}

 

BFS로 풀이

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
       bfs로 구현시 걸음수를 세는 변수가 필요하지않다,최소값을 저장할 변수또한 필요없다.
       벽인지 지나갈수있는길인지 체크하는 map변수에 걸음수를 추가해줘도되고, 아니면 걸음수만을 따로저장할 2차원배열을 생성해주면된다.
       모든 탐색이 끝났을때 목적지의 걸음수가 해당 목적지를 가기 위한 가장 적은 이동횟수일것이다.
     */

    static int[][] map;
    static int m,n;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = input[0];
        m = input[1];
        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            int[] position = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt)
                .toArray();
            map[i] = position; // 한번에 넘겨준다.
        }
    }

    static void solve() throws IOException {
        bfs(0, 0);
        bw.write(map[n-1][m-1]+""); // 목적지에 담긴값을 출력한다.
    }

    static void bfs(int x, int y) throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y}); //시작위치 넣어준다.
        visited[x][y] = true;

        while (!q.isEmpty()) { //시작위치부터 bfs를 하여 동서남북 갈수있는경로로 가는 모든 경우를 살펴본다.
            int[] current = q.poll();
            int currentX = current[0];
            int currentY = current[1];

            for (int i = 0; i < 4; i++) {
                int nextX = currentX + dx[i];
                int nextY = currentY + dy[i];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (!visited[nextX][nextY] && map[nextX][nextY] != 0) {
                        visited[nextX][nextY] = true; //큐에 넣으면서 방문처리한다. 큐에 중복되서 들어가지않게하기위함.
                        map[nextX][nextY] = map[currentX][currentY] + 1; // 다음칸은 이전칸의 이동횟수 +1 을 저장해준다.
                        q.add(new int[]{nextX, nextY});
                    }
                }
            }
        }

    }

}