[BackJoon] 백준 3055 탈출(BFS)

백준 BFS 문제

#3055- 탈출

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

사용한 개념

BFS개념을 사용했습니다.

문제에서의 포인트는 다음과 같습니다. 한 단계씩 시간이 지날 때마다 고슴도치는 한칸 이동할 수 있고, 물은 상하좌우 4방향 중 물이 넘칠 수 있는 곳에 넘칩니다. 여기서 중요한 것은 물이 한단계 이후에 넘칠 위치는 고슴도치가 이동 할 수 없다는 것이 포인트 입니다.

자 아래 2가지만 명심하면 문제는 쉽습니다.

1. DFS를 통해 단계가 진행될 때, 고슴도치, 물 이 움직일 수 있는 조건들을 생각해 코딩합니다.

2. 여기서 물이 한단계 이후 넘칠 공간에는 고슴도치가 이동할 수 없기 때문에 물을 먼저 넘치게하고 그다음! 고슴도치가 움직이는 매커니즘으로 작동하게 한다!!

여기서 2번 조건을 만족하려면 어떻게 할까요..? 다른 소스들을 참고해보니 큐를 2개를 쓰거나, BFS를 2번 돌리던데, 저는 그렇게 하지않고 하나의 큐에 고슴도치와 물 모두 움직여야하는 포인트들을 넣을 겁니다. 다만!! 먼저 물을 움직이게 하기 위해 물의 포인트를 먼저 넣어주고 그 다음 고슴도치 위치를 넣어줍니다. 그러면 큐의 선입선출이라는 특징 때문에 물이 먼저 움직이고, 그 다음으로 고슴도치가 움직일 수 있게 됩니다.

또한, 현재 고슴도치가 위치한 좌표에서 다음 단계를 진행할 때, 고슴도치는 다른곳으로 이동하지만 물이 먼저 넘치기 때문에 현재 고슴도치가 위치한 좌표에 물이 표시되고 그 다음 고슴도치를 이동시키기 위해 해당 좌표를 검색하면 이미 물이 표시되어, 고슴도치를 이동할 수 없는 문제를 해결하기 위해 MyPoint 라는 클래스를 선언하고 해당 좌표가 일전에 물이였는지, 고슴도치였는지 알 수 있는 c라는 변수값을 두어 문제를 해결 할 수 있게끔 했습니다.

아래는 전체소스입니다. 궁굼하신 점은 댓글 남겨주세요~

전체소스

package BackJoon.BFS;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BackJoon_3055 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int h = sc.nextInt(); //행의 갯수
		int w = sc.nextInt(); //열의 갯수
		
		sc.nextLine();
		
		char[][] map = new char[h][w];
		int[][] count = new int[h][w];
		
		for(int i=0; i<h; i++){
			String str = sc.nextLine();
			for(int j=0; j<w; j++){
				map[i][j] = str.charAt(j);
			}
		}
		
		BFS(map, count, w, h);

		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				if(map[i][j] =='D'){
					if(count[i][j]==0) {
						System.out.println("KAKTUS");
						return;
					}
					System.out.print(count[i][j]);
					return;
				}
			}
		}

	}
	
	
	static int[] directX = {0, -1, 0, 1};
	static int[] directY = {1, 0, -1, 0};
	private static void BFS(char[][] map, int[][] count, int w, int h) {
		
		Queue<MyPoint> q = new LinkedList<>();
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				if(map[i][j] == '*') q.add(new MyPoint(i, j, '*'));
			}
		}
		
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				if(map[i][j] == 'S') q.add(new MyPoint(i, j, 'S'));
			}
		}
		
		while(!q.isEmpty()){
	
			MyPoint p = q.poll();
			for(int i=0; i<4; i++){
				int mvX = p.x + directX[i];
				int mvY = p.y + directY[i];
			
		
				if(-1 < mvX && mvX < h && -1 < mvY && mvY < w){

					if(p.c == 'S') {
						if((map[mvX][mvY] == '.' || map[mvX][mvY] == 'D') && map[mvX][mvY] != 'X'  ){
							count[mvX][mvY] = count[p.x][p.y] + 1;
							if(map[mvX][mvY] == 'D') return;
							map[mvX][mvY] = 'S';
							q.add(new MyPoint(mvX, mvY, p.c));
						}
					}

					if(p.c == '*'){
						if(map[mvX][mvY] != 'D' && map[mvX][mvY] != '*' && map[mvX][mvY] != 'X'){
							map[mvX][mvY] = '*';
							q.add(new MyPoint(mvX, mvY, p.c));
						}	
					}
			
				}
			}	
		}
	}
	static class MyPoint{
		int x;
		int y;
		char c;
		public MyPoint(int x, int y, char c) {
			this.x = x;
			this.y = y;
			this.c = c;
		}
		
		
	}

}