[백준] 13460 - 구슬 탈출 2 (JAVA)

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

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

백트래킹을 사용했다.

2. 사고과정

문제를 봤는데 백트래킹밖에 생각나지 않았다.
N과 M의 크기가 작으므로 백트래킹으로도 충분히 풀 수 있을 것이라고 생각했다. 문제를 다 풀고 다른 사람들은 BFS 로 많이들 풀었던데 내일 한 번 공부해 볼 예정이다.

먼저 구슬을 한 칸씩 이동시키는 데에 있어서 어떤 조건으로 움직여야하나를 가장 오래 고민했다. 어떤 것을 먼저 움직이냐에 따라 결과값이 천차만별로 달라지기 때문이다.

고민한 결과는 내가 움직이는 방향의 끝 좌표에 더 가까운 것을 먼저 이동시키는 것이다.
👉 파란 구슬이 더 가깝다면 파란 구슬을 먼저, 빨간 구슬이 더 가깝다면 빨간 구슬을 먼저 움직인다.

3. 풀이과정

1. 백트래킹으로 모든 경우의 수를 탐색. 10 초과로 탐색하면 안되므로 10 초과시 return
2. redFirst 라는 변수로 빨간 공을 먼저 움직일지, 파란 공을 먼저 움직일지 정함 ( 이후의 설명은 빨간 공을 먼저 움직인 경우에 대해서만 설명)
3. 먼저 움직이는 공을 다음 map이 . 인 경우 계속 탐색.
4. . 이 아니라면 탐색을 종료하고 처음의 위치와 멈춘 위치에 있는 값을 교환.
5. 만약 빨간 공의 다음 위치가 O 인 경우 잠시 동안 빨간 공을 . 로 비워둠. (이유는 8번에서 말함.)
6. 이제 파란 공을 탐색. 다음 map 이 . 인 경우 계속 탐색. .이 아니라면 멈춤.
7. 만약 파란 공의 다음 위치가 O인 경우 error 라는 boolean 변수를 true로 바꿔줌. 이 error는 파란 공이 구멍에 도착한 경우는
   (1) 최솟값을 갱신해주지 않음. (2) 다음 DFS 를 수행하지 않음. 2가지 역할을 수행함.
8. 이제 왜 잠시 빨간 공을 .로 바꿨는지 설명하는데, 빨간 공과 파란 공이 동시에 O 에 도착한 경우를 생각하기 위해서임. 6번 과정에서 다음 위치가 .인 경우만 수행하므로 중간에 빨간 공이 같은 행이나 열에 있었을 때, 동시에 구멍에 들어가는 걸 인지해야함.
9. error (파란 공이 구멍에 들어간 경우) 가 없고 빨간 공의 다음 위치가 구멍인 경우 min 값을 갱신 함.
10. 이제 공을 옮기는 작업을 모두 수행했음. 만약 에러가 발생한 적이 없다면 원래 빨간 공의 위치를 다시 R 로 바꿔줌.
11. Result 타입의 Class를 반환. 바뀐 2차원 map 과 boolean 타입의 error 를 반환
12. 백트래킹을 할 때 error가 true 라면 백트래킹을 수행하지 않음. 백트래킹 시 error 가 false 인 경우만 수행함.
13. min의 최솟값은 INF 인데, 만약 백트래킹을 모두 수행해도 min이 INF 라면 빨간 공이 구멍에 들어간 경우가 없는 것임. 이 경우에는 -1 출력. 이 외에는 min 값을 출력

4. 소스코드

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

class Result {
	char map[][];
	boolean error;
	Result(char map[][],boolean error){
		this.map=map;
		this.error=error;
	}
}

public class Main {
	static char map[][];
	static int min=Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {

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

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		map=new char[N][M];
		for(int i=0;i<N;i++) {
			String word=br.readLine();
			map[i]=word.toCharArray();
		}


		backtracking(1,map);

		if(min==Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);

	}
	public static void backtracking(int depth,char map[][]) {
		if(depth>10) {
			return;
		}
		char newMap1[][]=new char[map.length][map[0].length];
		char newMap2[][]=new char[map.length][map[0].length];
		char newMap3[][]=new char[map.length][map[0].length];
		char newMap4[][]=new char[map.length][map[0].length];

		int blueY=0;
		int blueX=0;
		int redY=0;
		int redX=0;
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[0].length;j++) {
				newMap1[i][j]=map[i][j];
				newMap2[i][j]=map[i][j];
				newMap3[i][j]=map[i][j];
				newMap4[i][j]=map[i][j];
				if(map[i][j]=='R') {
					redY=i;
					redX=j;
				}
				if(map[i][j]=='B') {
					blueY=i;
					blueX=j;
				}

			}
		}
		Result res1= left(blueY,blueX,redY,redX,newMap1,depth);
		Result res2= right(blueY,blueX,redY,redX,newMap2,depth);
		Result res3= up(blueY,blueX,redY,redX,newMap3,depth);
		Result res4= down(blueY,blueX,redY,redX,newMap4,depth);
		if(!res1.error) backtracking(depth+1,res1.map);
		if(!res2.error) backtracking(depth+1,res2.map);
		if(!res3.error) backtracking(depth+1,res3.map);
		if(!res4.error) backtracking(depth+1,res4.map);


	}
	public static void change(int beforeY,int beforeX,int afterY,int afterX, char map[][]) {
		char temp=map[beforeY][beforeX];
		map[beforeY][beforeX]=map[afterY][afterX];
		map[afterY][afterX]=temp;
	}
	public static Result left(int blueY,int blueX,int redY,int redX,char map[][],int depth) {
		boolean redFirst=blueX>=redX?true:false;
		boolean error=false;
		if(redFirst) {
			int nowRedx=redX;
			int nowBluex=blueX;
			while(map[redY][redX-1]=='.') 
				redX--;
			change(redY,nowRedx,redY,redX,map);
			if(map[redY][redX-1]=='O') map[redY][redX]='.';

			while(map[blueY][blueX-1]=='.') 
				blueX--;
			change(blueY,nowBluex,blueY,blueX,map);
			if(map[blueY][blueX-1]=='O') 
				error=true;
			if(map[redY][redX-1]=='O'&&!error) {
				min=Math.min(depth,min);
			}

		}else {
			int nowBluex=blueX;
			int nowRedx=redX;
			while(map[blueY][blueX-1]=='.') 
				blueX--;
			change(blueY,nowBluex,blueY,blueX,map);

			while(map[redY][redX-1]=='.') 
				redX--;
			change(redY,nowRedx,redY,redX,map);

			if(map[blueY][blueX-1]=='O') 
				error=true;
			if(map[redY][redX-1]=='O'&&!error) {
				min=Math.min(depth,min);
			}

		}
		if(!error) map[redY][redX]='R';
		Result temp=new Result(map,error);
		return temp;

	}
	public static Result right(int blueY,int blueX,int redY,int redX,char map[][],int depth) {
		boolean redFirst=redX>=blueX?true:false;
		boolean error=false;
		if(redFirst) {
			int nowRedx=redX;
			int nowBluex=blueX;
			while(map[redY][redX+1]=='.') 
				redX++;
			change(redY,nowRedx,redY,redX,map);
			if(map[redY][redX+1]=='O') map[redY][redX]='.';
			while(map[blueY][blueX+1]=='.') 
				blueX++;
			change(blueY,nowBluex,blueY,blueX,map);
			if(map[blueY][blueX+1]=='O') 
				error=true;
			if(map[redY][redX+1]=='O'&&!error) {
				min=Math.min(depth,min);
			}
			
		}else {
			int nowBluex=blueX;
			int nowRedx=redX;
			while(map[blueY][blueX+1]=='.') 
				blueX++;
			change(blueY,nowBluex,blueY,blueX,map);

			while(map[redY][redX+1]=='.') 
				redX++;
			change(redY,nowRedx,redY,redX,map);


			if(map[blueY][blueX+1]=='O') 
				error=true;
			if(map[redY][redX+1]=='O'&&!error) {
				min=Math.min(depth,min);
			}
		}
		if(!error) map[redY][redX]='R';
		Result temp=new Result(map,error);
		return temp;
	}
	public static Result up(int blueY,int blueX,int redY,int redX,char map[][],int depth) {
		boolean redFirst=redY<=blueY?true:false;
		boolean error=false;
		if(redFirst) {
			int nowRedY=redY;
			int nowBlueY=blueY;
			while(map[redY-1][redX]=='.') 
				redY--;
			change(nowRedY,redX,redY,redX,map);
			if(map[redY-1][redX]=='O') map[redY][redX]='.';
			while(map[blueY-1][blueX]=='.') 
				blueY--;
			change(nowBlueY,blueX,blueY,blueX,map);
			if(map[blueY-1][blueX]=='O') 
				error=true;
			if(map[redY-1][redX]=='O'&&!error) {
				min=Math.min(depth,min);
			}

		}else {
			int nowBlueY=blueY;
			int nowRedY=redY;
			while(map[blueY-1][blueX]=='.') 
				blueY--;
			change(nowBlueY,blueX,blueY,blueX,map);
			while(map[redY-1][redX]=='.') 
				redY--;
			change(nowRedY,redX,redY,redX,map);
			
			if(map[blueY-1][blueX]=='O') 
				error=true;
			
			if(map[redY-1][redX]=='O'&&!error) {
				min=Math.min(depth,min);
			}
		}
		if(!error) map[redY][redX]='R';
		Result temp=new Result(map,error);
		return temp;
	}
	public static Result down(int blueY,int blueX,int redY,int redX,char map[][],int depth) {
		boolean redFirst=redY>=blueY?true:false;
		boolean error=false;
		if(redFirst) {
			int nowRedY=redY;
			int nowBlueY=blueY;
			while(map[redY+1][redX]=='.') 
				redY++;
			change(nowRedY,redX,redY,redX,map);
			if(map[redY+1][redX]=='O') map[redY][redX]='.';
			while(map[blueY+1][blueX]=='.') 
				blueY++;
			change(nowBlueY,blueX,blueY,blueX,map);
			if(map[blueY+1][blueX]=='O') 
				error=true;
			if(map[redY+1][redX]=='O'&&!error) {
				min=Math.min(depth,min);
			}
		}else {
			int nowBlueY=blueY;
			int nowRedY=redY;
			while(map[blueY+1][blueX]=='.') 
				blueY++;
			change(nowBlueY,blueX,blueY,blueX,map);
			while(map[redY+1][redX]=='.') 
				redY++;
			change(nowRedY,redX,redY,redX,map);
			if(map[blueY+1][blueX]=='O') 
				error=true;
			if(map[redY+1][redX]=='O'&&!error) {
				min=Math.min(depth,min);
			}
		}
		if(!error) map[redY][redX]='R';
		Result temp=new Result(map,error);
		return temp;
	}

}

5. 결과

6. 회고

코드가 250줄 . . .
드럽기도 드럽다. 이거 못 풀었으면 오늘 못 자는데 겨우 풀어서 잘 수 있게 됐다.
이 문제를 도대체 어떻게 BFS 로 푼다는 건지 아직까지는 모르겠다. 내일 다른 사람 코드를 보면서 공부해 볼 예정.

진짜 아직 해석까진 안하고 다른 사람 코드들 몇개 봤는데 진짜 세상에 똑똑한 사람은 많고 많나보다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212