[백준] 2665 미로만들기 - JAVA

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

2665번: 미로만들기

🌟1261 알고스팟 문제와 거의 유사하다. 

 

 

[알고리즘]

• 검은 방을 최소한으로 흰방으로 바꾸고 이동하기 위해 최소비용 BFS 알고리즘 적용 

---

 

[설계]

• 2차원 배열의 (0,0) 부터 이동 
  1. 검은 방: 흰방으로 바꾸고 (map[x][y] = 1) , 바꾼 방 갯수+1 후 이동 
  2. 흰 방: 그냥 이동
• 우선순위큐에 의해 가장 먼저 (n-1, n-1) 나왔을 때, 바꾼 방의 갯수가 최소값 (=답) 
• Room 클래스 
  1. 현재 위치, 현재까지 바꾼 방의 총 갯수 저장 
  2. Comparable 인터페이스를 구현하여 방 갯수 오름차순 정렬 
  3. 우선순위큐에 저장, 방의 갯수가 적을 수록 우선순위 ↑

---

 

[구현 과정]

• map[][] : 바둑판 모양의 방 정보를 저장할 int형 배열 (0은 검은방, 1은 흰 방)
• Room 클래스 : (x,y) = 위치, change = (x,y)까지 이동하는데에 바꾼 방의 갯수 

 

1. 입력받은 바둑판 모양의 방 정보를 map 배열에 저장 

 

2. 시작 위치인 map[0][0] 에서 BFS 탐색 시작 

 

3. Room 클래스를 담고 있는 우선순위큐와, 방문체크를 위한 visited 배열을 생성한다. 출발점을 큐에 add하고 방문체크 후 시작 

 

4. 큐가 빌 때까지 아래 과정을 반복한다. (bfs 탐색) 

• 큐에서 하나 poll (=큐에 들어있는 Room 객체 중 바꾼 방의 갯수가 가장 적은 것) 
• poll 한 위치가 목적지인 [n-1][n-1] 이라면, 바꾼 방의 갯수(change) 반환. (=우선순위큐에 의해 최소 갯수)
• 그렇지 않다면 사방탐색하며 이동 
  1. 만약 이동한 위치가 map 범위를 벗어나거나 방문했던 곳이라면 continue 
  2. 검은 방(=0) 일 경우: 흰 방(1)으로 바꾸고, 방문체크 후 큐에 삽입 (바꾼 방 갯수 change+1)
  3. 흰 방(=1) 일 경우: 방문체크 후 큐에 삽입 

 

 

5. 목적지까지 다다르는데 최소한으로 바꾼 방의 갯수, 즉 BFS 결과 그대로 출력 

 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static int map[][]; 
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};

	static class Room implements Comparable<Room>{
		int x;
		int y;
		int change;
		
		public Room(int x, int y, int change) {
			this.x=x;
			this.y=y;
			this.change=change;
		}

		@Override
		public int compareTo(Room o) {
			return this.change- o.change;
		}
	}
	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];
		for(int i=0; i<n; i++) {
			String s= br.readLine();
			for(int j=0; j<n; j++) {
				map[i][j] = s.charAt(j)-'0';  
			}
		}
		
		System.out.println(bfs()); 
		
		
	}//end of main
	
	private static boolean isOut(int x, int y) {
		return x<0 || x>=n ||y<0 || y>=n;
	}
	private static int bfs() {
		PriorityQueue<Room> que= new PriorityQueue<>();
		boolean visited[][] = new boolean[n][n]; 
		
		que.add(new Room(0,0,0));
		visited[0][0] = true; 
		
		while(!que.isEmpty()) {
			Room r= que.poll();
			int x= r.x;
			int y= r.y;
			int change= r.change;
			
			if(x==n-1 && y==n-1) return change; 
			
			for(int d=0; d<4; d++) {
				int nx = x+dx[d];
				int ny = y+dy[d];
				
				if(isOut(nx, ny)|| visited[nx][ny]) continue;
				
				visited[nx][ny] = true;
				//검은방일 경우, 흰방으로 바꾸어야함 
				if(map[nx][ny]==0) {
					map[nx][ny]=1; 
					que.add(new Room(nx,ny,change+1)); 
				}
				else que.add(new Room(nx,ny,change)); 
			}
 		}
		
		return -1;
	}
}//end of class