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

1. 소요시간 : 20분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다익스트라
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2665
8. 푼 날짜 : 2023.04.03

1. 사용한 자료구조 & 알고리즘

다익스트라 알고리즘, BFS 를 사용했다.

2. 사고과정

map(0,0) 에서 map(n-1,n-1) 로 가는 최소 거리가 아닌,
최소로 벽을 바꾸는 횟수를 출력해야한다.

처음에는 visited 배열로 최솟값을 갱신해주려고 했지만
그렇게 된다면 예를들어 50번만에 벽을 부수고 어딘가로 왔다면
그 위치에서 0~49개의 벽을 부숴서 도착한 visited 가 있는지 check 해줘야 한다. 최악의 경우에는 여기서 n이 50이니
50*50으로 2500번을 매번 이동할 때마다 확인해줘야 하므로

💡 boolean 형의 visited 대신, int 형으로 좌표에 온 최소값을 기록하고 있다가,
나보다 짧게 좌표에 온 경우가 있을 때 갱신해 줘야 한다.

👉 다익스트라 알고리즘의 개념

3. 풀이과정

1. map[i][j]의 입력을 받는다. min의 2차원 배열도 함께 가져야 하는데, 현재 위치에 도달한 최솟값을 기록해주기 위함이다. 초깃값은 INF 로 한다.
2. map[0][0] 에서 BFS 를 수행한다. 여기서, map[0][0] 이 흰 돌이라는 가정이 없으니, map[0][0] 이 검은 돌인 경우와 흰 돌일 경우로 나누어서 queue에 넣는다.
   👉 검은 돌일 경우 1개 바꿔서 넣고, 흰 돌일 경우 바꾸지 않은 상태로 넣음
3. 이제 다익스트라 알고리즘을 적용한다. 이 경우에도 다음 좌표가 흰 돌인지, 검은 돌인지에 따라서 다르게 갱신한다.
4. 최소 거리를 구하는 것과는 다르게, 끝 좌표에 도달했다고 바로 return 해줘서는 안 된다. 더 느리게 왔지만 더 적게 검은 돌을 바꿔서 도달한 경우가 있을 수 있기 때문이다. 따라서 queue가 비기 전까지 수행해야 한다.
5. queue가 비었다면, min[n-1][n-1] 의 값을 출력한다.

4. 소스코드

import java.util.*;
import java.io.*;
class Drill {
	int y;
	int x;
	int drill;
	Drill(int y,int x,int drill){
		this.y=y;
		this.x=x;
		this.drill=drill;
	}
}

public class Main {
	static char map[][];
	static int xx[]= {-1,1,0,0};
	static int yy[]= {0,0,-1,1};
    static int min[][];
	public static void main(String[] args) throws IOException {

		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		int n=Integer.parseInt(br.readLine());
		map=new char[n][n];
		min=new int[n][n];
		for(int i=0;i<n;i++) {
			String word=br.readLine();
			for(int j=0;j<n;j++) {
				map[i]=word.toCharArray();
			}
		}
		
		bfs();
		System.out.println(min[n-1][n-1]);
		
	}
	public static void bfs() {
		Queue<Drill> queue=new LinkedList<>();
	
		for(int i=0;i<min.length;i++)
			Arrays.fill(min[i],1000000);
		//1은 흰방 0은 검은 방
		if(map[0][0]=='0') {
			queue.add(new Drill(0,0,1));
			min[0][0]=1;
		}
		else {
			queue.add(new Drill(0,0,0));
			min[0][0]=0;
		}
		
		while(!queue.isEmpty()) {
			Drill temp=queue.poll();
			int prevY=temp.y;
			int prevX=temp.x;
			int drill=temp.drill;
			for(int i=0;i<4;i++) {
				int nextY=prevY+yy[i];
				int nextX=prevX+xx[i];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
					continue;
				if(map[nextY][nextX]=='0'&&drill+1>=min[nextY][nextX])
					continue;
				if(map[nextY][nextX]=='1'&&drill>=min[nextY][nextX])
					continue;
				
				
				if(map[nextY][nextX]=='1') {
					queue.add(new Drill(nextY,nextX,drill));
					min[nextY][nextX]=drill;
				}
				else {
					queue.add(new Drill(nextY,nextX,drill+1));
					min[nextY][nextX]=drill+1;
				}
				
				
			}
		}


		
	}
}

5. 결과

첫 번째 제출 -> map을 int형으로 선언
두 번째 제출 -> map을 char형으로 선언
✨ map이 0 혹은 1 일 수밖에 없으니 char로 선언하는게 더 깔끔하다.

6. 회고

다익스트라 알고리즘을 2차원 배열에서 하는 건 처음이었는데
사실 알고리즘을 생각했을 때 최소값을 갱신해줘야 겠다고 생각만 했지
이게 다익스트라 알고리즘일거라고 생각하진 않고 풀었는데
풀고나서 다른 사람들 풀이 보니까 내가 한 것이 그냥 다익스트라 알고리즘을 쓴 거였다.

다익스트라 알고리즘 -> 시작 노드가 정해져 있을 때, 그 노드에서 다른 노드로 갈 때 최소 비용을 구하는 알고리즘 !

BFS 가 끝나고 min을 출력해 보면 실제로 다른 노드로 가는 최소 비용임을 알 수 있다!