[알고리즘] 백준 2178 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];

        for (int i = 1; i < n + 1; i++) {
            s = br.readLine();

            for (int j = 1; j < m + 1; j++) {
                map[i][j] = s.charAt(j - 1) - '0';
            }
        }

        int temp = bfs(1, 1);
        System.out.println(map[n][m]);
    }

    public static int bfs(int x, int y) {
        int count = 0;
        visited[x][y] = true;
        Queue<Location> qu = new LinkedList<Location>();
        qu.add(new Location(x, y));

        while (!qu.isEmpty()) {
            Location location = qu.poll();

            if (location.x == n && location.y == m)
                return count;

            count++;

            for(int i = 0; i < 4; i++) {
                if (location.x + dx[i] > 0 && location.x + dx[i] < n + 1 && location.y + dy[i] > 0 && location.y + dy[i] < m + 1) {
                    if (map[location.x + dx[i]][location.y + dy[i]] == 1 && !visited[location.x + dx[i]][location.y + dy[i]]) {
                        qu.add(new Location(location.x + dx[i], location.y + dy[i]));
                        visited[location.x + dx[i]][location.y + dy[i]] = true;
                        map[location.x + dx[i]][location.y + dy[i]] = map[location.x][location.y] + 1;
                    }
                }
            }
        }

        return count;
    }

    public static class Location {
        int x;
        int y;

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

1,1에서 출발하여 N, M까지 도달하는데 까지 지나야 하는 최소의 칸 수를 구하는 프로그램이다.

 

최단경로를 찾아야 하기 때문에 이 문제는 BFS를 통해서 풀어야 한다.

 

이 문제를 풀 때 중요한 논리는

 

int nx = location.x + dx[i]

 

int ny = location.x + dy[i]

 

라고 하였을 때, map[nx][ny] = map[location.x][location.y] + 1이라는 것이다.

 

위를 통해 탐색 순서를 굳이 신경써주지 않더라도 칸수를 넘어갈 때 마다 걸리는 cost를 따라갈 수 있다.