[백준][2178번] 미로탐/

문제 URL

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

dfs

(1,1)에서 (n,m)으로 가는 가장 빠른 길을 구하는 문제이다.

• DFS 탐색으로는 문제를 풀 수 없다. BFS탐색을 이용해야한다.
• BFS의 단계별로 진행된다는 사실을 이용하면된다.
• BFS는 모든 정점을 ‘단 한번만’ 방문한다. 또 다시 방문을 허용하면 시간복잡도는 증가하며 BFS가 아닌 브루트포스라고 부른다.

public static void bfs(int[][] map, int[][] check, int startX, int startY, int n, int m) {
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(startX, startY,1));

        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            int cnt = p.cnt;

            for (int i = 0; i < 4; i++) {
                int cx = x + dx[i];
                int cy = y + dy[i];
                if (0 <= cx && cx < n && 0 <= cy && cy < m) {
                    if (map[cx][cy] == 1 && check[cx][cy] == 0) {
                        q.add(new Pair(cx, cy,cnt+1));
                        check[cx][cy] = cnt+1;
                    }
                }
            }
        }
    }

전체 풀이

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static public class Pair {
        public int x;
        public int y;
        public int cnt;

        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws IOException {
            String[] str = br.readLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int m = Integer.parseInt(str[1]);
            int[][] map = new int[n][m];
            int[][] check = new int[n][m];

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

            bfs(map,check,0, 0, n, m);
            System.out.println(check[n-1][m-1]);
        }

    public static void bfs(int[][] map, int[][] check, int startX, int startY, int n, int m) {
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(startX, startY,1));

        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            int cnt = p.cnt;

            for (int i = 0; i < 4; i++) {
                int cx = x + dx[i];
                int cy = y + dy[i];
                if (0 <= cx && cx < n && 0 <= cy && cy < m) {
                    if (map[cx][cy] == 1 && check[cx][cy] == 0) {
                        q.add(new Pair(cx, cy,cnt+1));
                        check[cx][cy] = cnt+1;
                    }
                }
            }
        }
    }
}

다른풀이

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        sc.nextLine();
        for (int i=0; i<n; i++) {
            String s = sc.nextLine();
            for (int j=0; j<m; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        int[][] dist = new int[n][m];
        boolean[][] check = new boolean[n][m];
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(0, 0));
        check[0][0] = true;
        dist[0][0] = 1;
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (check[nx][ny] == false && a[nx][ny] == 1) {
                        q.add(new Pair(nx, ny));
                        dist[nx][ny] = dist[x][y] + 1;
                        check[nx][ny] = true;
                    }
                }
            }
        }
        System.out.println(dist[n-1][m-1]);
    }
}