[Baekjoon] 2665_미로만들기

Gold IV

문제(출처: https://www.acmicpc.net/problem/2665)

---

< 미로 만들기>

 

문제 풀이

 

bfs를 활용하여 모든 방을 탐색한다. 흰 방이면 바꾸어야 할 최소의 수를 전 값으로 그대로 유지하고 검은 방인 경우에는 바꾸어야 할 최소의 수를 전 값 +1로 바꿔준다. 이때 최소의 수를 구하기 위해 조건을 잘 설정한다.

 

 

 - my solution (Java)

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

public class _2665_ { // 미로만들기
	static boolean arr[][];
	static int result[][], n;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		n=Integer.parseInt(bf.readLine());
		arr=new boolean[n][n];
		result=new int[n][n];

		for(int i=0; i<n; i++) {
			String s=bf.readLine();
			for(int j=0; j<n; j++) {
				if(s.charAt(j)=='0') arr[i][j]=false; // 검은 방
				else arr[i][j]=true; // 흰 방
				result[i][j]=-1;
			}
		}
		search(0,0);
		System.out.println(result[n-1][n-1]);
	}

	private static void search(int i, int j) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {i,j});
		result[i][j]=0;

		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int k=0; k<4; k++) {
				int x=temp[0]+dx[k];
				int y=temp[1]+dy[k];
				if(x>=0 && x<n && y>=0 && y<n) {
					if(arr[x][y]) { // 흰 방
						if(result[x][y]==-1 || result[x][y]>result[temp[0]][temp[1]]) {
							result[x][y]=result[temp[0]][temp[1]];
							queue.add(new int[] {x,y});
						}
					}else { // 검은 방
						if(result[x][y]==-1 || result[x][y]>result[temp[0]][temp[1]]+1) {
							result[x][y]=result[temp[0]][temp[1]]+1;
							queue.add(new int[] {x,y});
						}
					}
				}
			}
		}
	}
}

 

• Main
  • n 입력
  • arr : 수열 입력
  • result: 바꾸어야 할 최소의 검은 방의 수
  • search 함수 호출 후 result [n-1][n-1] 출력
• search 
  
  • queue에 시작 위치인 (0,0) 넣고 result를 0으로 저장
  • queue가 빌 때까지 반복 -> 상하좌우 탐색 -> 흰 방일 때 아직 방문하지 않은 곳이거나 바꾸어야 할 검은 방의 수가 최소라면 update/ 검은 방일 때 아직 방문하지 않은 곳이거나 바꾸어야 할 검은 방의 수가 최소라면 update

---

생각🤔

 

---