[백준 2665] 미로만들기 (Java, BFS)

 

 

 

[백준 2665] 미로만들기 (Java, BFS)

 

문제 출처 : 링크

2665번: 미로만들기

 

시작부터 끝이 정해져 있고, 시작 방부터 끝 방까지 방의 색을 최소로 바꿔서 이동시켜야 하는 문제다.

 

BFS라는거는 바로 알 수 있지만, 단순하게 생각하면 까다로울 수 있는 문제다.

평소처럼 boolean으로 visit 배열을 만들어 체크하는 것이 아닌, int형으로 각 위치마다 방을 바꾼 횟수를 저장시키며 나아가는 방법을 익힌 문제..!

 

시작할 때 visit 배열을 모두 무한대 값으로 초기화 해두고, BFS를 진행하면서 해당 위치에 최소값을 저장해나가는 것이 포인트다.

 

벽을 만났을 때, 해당 벽을 기준으로 visit 배열의 해당 위치 값을 +1로 증가시키며 탐색을 진행한다.

 

BFS는 큐가 완전히 빈 상태가 될 때까지 상하좌우로 뻗어나가기 때문에, 같은 위치가 여러번 들어올 것이다. 이때 들어오는 값들 중 가장 최소 값을 저장하면 된다. (즉 이미 값이 존재할 때, 새로 들어온 값보다 작으면 continue)

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main_2665_미로만들기_김규석 {
 
    static class Block {
        int y;
        int x;
 
        Block(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
 
    static int N;
    static int[][] map;
    static int[][] visit;
 
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static int cnt;
    static int min;
    
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
 
        map = new int[N][N];
        visit = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                visit[i][j] = Integer.MAX_VALUE; // 이동 수 저장할 visit 배열은 무한대로 초기화
            }
        }
        
        bfs(0,0);
        
        System.out.println(visit[N-1][N-1]);
    }
 
    public static void bfs(int y, int x) {
 
        Queue<Block> q = new LinkedList<>();
 
        q.add(new Block(y, x));
        visit[0][0] = 0; // 시작 값은 0
 
        while (!q.isEmpty()) {
 
            Block b = q.poll();
 
            for (int i = 0; i < 4; i++) {
                int ny = b.y + dy[i];
                int nx = b.x + dx[i];
 
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                    continue;
                
                if(visit[ny][nx] <= visit[b.y][b.x]) continue; // 만약 옮기기 전의 값보다 옮긴 값에 이미 더 작은 값이 들어있으면 continue
                
                if (map[ny][nx] == 1) { // 이동할 수 있는 곳이면 visit은 이전값 넣어줌
                    q.add(new Block(ny, nx));
                    visit[ny][nx] = visit[b.y][b.x];
                }
                else { // 이동할 수 없는 벽이면, 값을 +1
                    q.add(new Block(ny, nx));
                    visit[ny][nx] = visit[b.y][b.x] + 1;
                }
            }
 
        }
 
    }
 
 
}