[백준] 2665번 - 미로만들기 (Java)

 

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

2665번: 미로만들기

 

<풀이>

검은 방을 변경하는 로직을 어떻게 가져 가야할 지 고민이 되었다.

처음엔 백준 14502 연구소 문제와 비슷한 유형으로 생각하고 아이디어를 생각해보았다.

랜덤하게 검은방 하나씩 변경하고 BFS탐색을 하는 식으로 진행해 봤는데 14502와는 차이점이 그 문제는 문 3개가 되면 탐색을 시작한다는 명확한 재귀탈출 조건이 있었고, 이 문제는 조건 세우기가 애매했다.

검은방의 위치, 갯수... 랜덤하게 진행하기에는 변수가 너무 많았다.

 

1시간 넘게 고민하다가 결국 검색을 해서 다른 사람들은 어떻게 풀었는지 확인을 했다.

방문배열을 사용하지 않고, 검은 방 변경횟수를 담는 배열을 대신 사용해서 BFS탐색을 진행하는 방법을 사용했다.

map과 동일한 사이즈인 dist[N][N]을 선언해서, BFS탐색을 해나가면서 검은방을 만나면 dist[x][y] +1을 해준다.

단, 방문 조건은 방문지역의 방 변경횟수가 지금보다 반드시 커야 할 것. 그래야지 방문해서 횟수를 줄일 가능성이 있기 때문이다. 지금과 같거나 더 작으면 개선의 가능성이 없으므로 그 지역은 놔두고 다른 지역을 탐색한다.

 

BFS응용문제 (벽 세우기 문제도 그렇고 이번 문제도)는 확실히 알로리즘 센스가 필요한 것 같다. 이런 유형은 특징을 메모해 두고 비슷한 유형이 나오면 바로 떠올릴 수 있도록 연습하자.

 

<코드>

    1 	import java.util.*;
    2 	 
    3 	public class Main {
    4 	    static int N;
    5 	    static int map[][];
    6 	    static int dist[][]; // 검은방 변경횟수 기록
    7 	
    8 	    class Node {
    9 	        int x, y;
   10 	        Node (int x, int y) {
   11 	            this.x = x;
   12 	            this.y = y;
   13 	        }
   14 	    }
   15 	    void InputData(){
   16 	        Scanner sc = new Scanner(System.in);
   17 	        N = sc.nextInt();
   18 	        map = new int[N][N];
   19 	        for (int i=0; i<N; i++) {
   20 	            String str = sc.next();
   21 	            for (int j=0; j<N; j++) {
   22 	                map[i][j] = str.charAt(j)-'0';
   23 	            }
   24 	        }
   25 	        sc.close();
   26 	    }
   27 	
   28 	    static int dx[] = {-1, 0, 1, 0};
   29 	    static int dy[] = {0, 1, 0, -1};
   30 	    int BFS() {
   31 	        Queue<Node> Q = new LinkedList<>();
   32 	        Q.offer(new Node(0, 0)); // 시작위치 큐에 삽입
   33 	        dist[0][0] = 0; // 검은방 변경횟수를 0으로 저장
   34 	
   35 	        while (!Q.isEmpty()) {
   36 	            Node now = Q.poll();
   37 	            for (int i=0; i<4; i++) {
   38 	                int nx = now.x + dx[i];
   39 	                int ny = now.y + dy[i];
   40 	                // map 벙위를 벗어나면 패스
   41 	                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
   42 	                // 이동할 위치의 방변경횟수가 지금과 같거나 작으면 패스
   43 	                // 변경횟수가 더 클경우에만 개선의 여지가 있음.
   44 	                if (dist[nx][ny] <= dist[now.x][now.y]) continue; 
   45 	
   46 	                // 흰방이면 변경횟수를 똑같이 유지
   47 	                if (map[nx][ny] == 1) {
   48 	                    dist[nx][ny] = dist[now.x][now.y];
   49 	                }
   50 	                // 검은방이면 변경횟수+1해서 업데이트
   51 	                else {
   52 	                    dist[nx][ny] = dist[now.x][now.y] + 1;
   53 	                }
   54 	                Q.offer(new Node(nx, ny));
   55 	            }
   56 	        }
   57 	        return dist[N-1][N-1];
   58 	    }
   59 	
   60 	    static final int INF = Integer.MAX_VALUE;
   61 	    void Solve() {
   62 	        // dist 배열 큰수로 초기화
   63 	        dist = new int[N][N];
   64 	        for (int i=0; i<N; i++) {
   65 	            for (int j=0; j<N; j++) {
   66 	                dist[i][j] = INF;
   67 	            }
   68 	        }
   69 	        // BFS 탐색 시작
   70 	        int ans = BFS();
   71 	        System.out.println(ans);
   72 	    }
   73 	    public static void main(String[] args){
   74 	        Main m = new Main();
   75 	        m.InputData();              //  입력 함수 Input fuction
   76 	        m.Solve();//  코드를 작성하세요 Write the code
   77 	 
   78 	    }
   79 	}