[백준] 미로 탐색 - Silver 1

[jusung-c]

문제 링크

https://www.acmicpc.net/problem/2178

문제 조건

0과 1로 이루어진 N x M 크기의 map이 주어질 때 (1, 1)에서 출발해서 (N, M) 위치로 이동해야 한다.

1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸일 때 지나야 하는 최소의 칸 수를 구하라

• N, M(2 ≤ N, M ≤ 100)

---

아이디어

시작점도 정해져있고, 도착점도 정해져 있으므로 BFS를 진행하면서 dist 배열을 통해 최소 이동 횟수를 구하면 된다.

---

시간 복잡도

정점: O(NM)
간선: O(NM*4)

따라서 시간, 공간 복잡도는 모두 O(N*M)으로 시간 안 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, M;
    static int[][] map, dist;
    static boolean[][] visit;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = s.charAt(j - 1) - '0';
            }
        }

        dist = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dist[i][j] = -1;
            }
        }
    }

    private static void bfs(Point p) {
        Queue<Point> que = new LinkedList<>();
        que.add(p);
        visit[p.x][p.y] = true;
        dist[p.x][p.y] = 1;

        while (!que.isEmpty()) {
            p = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
                if (visit[nx][ny]) continue;
                if (map[nx][ny] != 1) continue;

                que.add(new Point(nx, ny));
                visit[nx][ny] = true;
                dist[nx][ny] = dist[p.x][p.y] + 1;
            }
        }
    }

    private static void pro() throws IOException {
        Point start = new Point(1, 1);

        bfs(start);

        bw.write(dist[N][M] + " ");
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}

사실 visit 배열 없이 dist 배열만으로도 방문했는 지 알 수 있다. dist 배열을 처음에 -1로 초기화했었기 때문에 dist값이 -1인 경우 방문하지 않았다고 생각하면 된다.

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, M;
    static int[][] map, dist;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = s.charAt(j - 1) - '0';
            }
        }

        dist = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dist[i][j] = -1;
            }
        }
    }

    private static void bfs(Point p) {
        Queue<Point> que = new LinkedList<>();
        que.add(p);
        dist[p.x][p.y] = 1;

        while (!que.isEmpty()) {
            p = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
                if (dist[nx][ny] != -1) continue;
                if (map[nx][ny] != 1) continue;

                que.add(new Point(nx, ny));
                dist[nx][ny] = dist[p.x][p.y] + 1;
            }
        }
    }

    private static void pro() throws IOException {
        Point start = new Point(1, 1);

        bfs(start);

        bw.write(dist[N][M] + " ");
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}