[백준] JAVA - 3055.탈출

생각

좌표에서 초기 물의 위치가 한개이상 주어질수 있습니다. 그렇기 때문에 BFS문제로 접근하되 물을 먼저 큐에 넣어주고 물의 이동에 대한 모든 처리를 끝내준 다음 고슴도치를 이동시켜야 하는 BFS 문제입니다.

(바로 전날에 7569 토마토문제를 풀어봐서 비슷한 유형이라고 느꼈습니다.)

 

처음에는 물과 고슴도치의 좌표 정보를 구분해서 줘야되나라고 생각하다가 (전에 풀어본 SWEA 배틀필드 문제가 생각났습니다.) 클래스 정보에 고슴도치와 물을 구분하는 값을 줘서 처리했습니다. (고슴도치 : 1, 물: 0)

 

1. 처음 입력을 받을때 큐에 물의 좌표를 넣습니다. 이때 구분값도 같이 넣어줍니다.

2. 마지막으로 고슴도치의 위치를 큐에 넣습니다. 마찬가지로 구분값도 같이 넣어줍니다.

3. 고슴도치의 이동 거리를 저장하는 dist 배열을 만들어주고 고슴도치의 시작좌표에 1 값으로 초기화 해줍니다.

4. BFS 를 시작하면서 물이 이동할수있는곳이고 방문을 안했던 곳이라면 큐에 다음 좌표를 넣어줍니다.

5. 다음 좌표가 고슴도치 굴인데 현재 좌표가 물이면 이동이 불가능합니다. 무시해주고 고슴도치라면 거리정보를 리턴합니다.

6. 거리 배열에 (다음 좌표 = 현재까지 온 거리 + 1) 을 해줍니다.

7. 큐가 다 비었을때까지 고슴도치가 도착하지 못했다면 'KAKTUS' 를 출력합니다.

 

 

package com.java.algorithm;

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

class Coordinate {
	int y;
	int x;
	int s; // 고슴도치 1 물 0
	public Coordinate(int y, int x, int s) {
		this.y = y;
		this.x = x;
		this.s = s;
	}
}

public class Baekjoon_3055_탈출 {
	/**
	 * 평지 : .
	 * 물 : * 
	 * 돌 : X 
	 * 굴 : D
	 * 고슴도치 : S
	 * 물,고슴도치는 돌을 통과할수없다.
	 * 물은 비버 소굴로 이동할수없다.
	 * 고슴도치 물이 찰 예정인곳으로 이동할수없음.
	 * bfs -> 물 먼저 이동시키고 고슴도치 이동가능한지 판단해준다. -> 물, 고슴도치 구분값으로 구분한다.
	 **/
	static Queue<Coordinate> q;
	static char[][] map;
	static int R;
	static int C;
	static int[][] dist;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] init = br.readLine().split(" ");
		R = Integer.parseInt(init[0]);
		C = Integer.parseInt(init[1]);
		
		map = new char[R][C];
		dist = new int[R][C];
		
		q = new LinkedList<>();
		int sy=0,sx=0;
		for (int i = 0; i < R; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < C; j++) {
				map[i][j] = s[j].charAt(0);
				if(map[i][j] == '*') {
					q.add(new Coordinate(i, j, 0));
					dist[i][j] = 0; //물 : 0 , 고슴도치 : 1
				}
				if(map[i][j] == 'S') {
					sy = i;
					sx = j;
				}
			}
		}
		q.add(new Coordinate(sy, sx, 1)); // 고슴도치위치를 큐 마지막에 넣는다.
		dist[sy][sx] = 1;
		bfs();
		
	}
	private static void bfs() {
		while(!q.isEmpty()) {
			Coordinate c = q.poll();
			int y = c.y;
			int x = c.x;
			int s = c.s;
			for (int k = 0; k < 4; k++) {
				int ny = y + dy[k];
				int nx = x + dx[k];
				//범위밖이면 이동 불가능
				if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
				//돌이거나 이미 갔던곳이면 이동 불가능
				if(map[ny][nx] == 'X' || dist[ny][nx] != 0) continue;
				//고슴도치 굴
				if(map[ny][nx] == 'D') {
					//물 이동 불가능
					if(s == 0) {
						continue;
					}
					//고슴도치 도착 끝!!
					System.out.println(dist[y][x]);
					return;
				}
				dist[ny][nx] = dist[y][x] + 1;
				q.add(new Coordinate(ny, nx, s));
				
			}
		}
		System.out.println("KAKTUS");
	}

}