백준 2178. 미로 탐색 :: 돼지개발자

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

"BFS를 활용한 최단거리 탐색"

해당 문제는 BFS를 활용해서 왼쪽 상단에서, 오른쪽 하단까지의 최단거리를 탐색하는 문제이다. 

BFS 에서 중요한 것은 갈 수 있나 없나를 체크하는 것과 중복 경로를 줄이는 것이다.

아래 풀이에서는 int형 배열 visited를 활용한다. visited 배열에는 해당 지점에 지나온 칸의 개수가 저장된다.

그 전에, 경로 A가 특정 지점 x, y 를 지날 때, 이미 저장된 visited[x][y] 에 값이 자신보다 더 작은 경우라면 경로 A는 더 이상

탐색할 필요가 없다. 이미 자신보다 더 최단 경로로 지나간 경우가 있기 때문에...

이러한 경우들을 생각해서 중복을 줄여준다. 그 외에 우선순위 큐를 활용해서 푸는 방법도 있다.

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;
 
class Main {
    
    static int N,M;
    static int[][] map;
    static int[][] visited;
    static Queue<Node> q = new LinkedList<>();
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int res;
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new int[N][M];
        
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        
        visited[0][0] = 1;
        q.add(new Node(0, 0, 1));
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            if(cur.x == N-1 && cur.y == M-1) {
                res = cur.cnt;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(!isRange(nx, ny) || visited[nx][ny] <= cur.cnt+1 || map[nx][ny] == 0)
                    continue;
                
                visited[nx][ny] = cur.cnt+1;
                q.add(new Node(nx, ny, cur.cnt+1));
            }
        }
        System.out.println(res);
    }
    
    static boolean isRange (int x, int y) {
        if( x < 0 || x >= N || y < 0 || y >= M) return false;
        return true;
    }
 
}
 
class Node {
    int x;
    int y;
    int cnt;
    
    Node(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}
 

우선순위 큐를 활용한 방법.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Main {
    
    static int N,M;
    static int[][] map;
    static boolean[][] visited;
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int res;
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        
        visited[0][0] = true;
        q.add(new Node(0, 0, 1));
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            if(cur.x == N-1 && cur.y == M-1) {
                res = cur.cnt;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == 0)
                    continue;
                
                visited[nx][ny] = true;
                q.add(new Node(nx, ny, cur.cnt+1));
            }
        }
        System.out.println(res);
    }
    
    static boolean isRange (int x, int y) {
        if( x < 0 || x >= N || y < 0 || y >= M) return false;
        return true;
    }
    
 
}
 
class Node implements Comparable<Node> {
    int x;
    int y;
    int cnt;
    
    Node(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
 
    @Override
    public int compareTo(Node o) {
        return this.cnt - o.cnt;
    }
    
    
    
}