[백준] G5 3055 탈출 (java)

www.acmicpc.net/problem/3055

3055번: 탈출

 

풀이

 

1) Queue를 2개 만들거임. 하나는 고슴도치, 하나는 물

2) 입력값을 받으면서 고슴도치가 나오면 queue에, 물이 나오면 queue2에 담는다. 동굴의 위치도 따로 저장한다.

3) bfs를 돌린다.

3-1) 고슴도치의 이동보다 물이 차는게 먼저다. 먼저 물을 채운다. (같은 너비를 다 채운후에 물을 채워야 한다)

3-2) 고슴도치의 이동경로를 queue에 담는다.

3-3) 동굴에 고슴도치가 도달하면 횟수(시간)을 출력하고 리턴

3-4) 3-3을 만족하지 못하고 bfs가 끝나면 "KAKTUS"를 출력.

 

 

주의사항

 

1) 고슴도치가 같은 너비에서 전부 이동을 해본후에 다음 깊이로 들어가면 물을 채워야한다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_3055_탈출 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int R,C, endR,endC;
	static char map[][];
	static boolean isVisited[][];
	static Queue<Node> queue = new LinkedList<>();
	static Queue<Node> queue2 = new LinkedList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		map = new char[R][C];
		isVisited = new boolean[R][C];
		for(int r=0; r<R; r++) {
			String line = input.readLine();
			for(int c=0; c<C; c++) {
				map[r][c] = line.charAt(c);
				if(map[r][c] == '*') {
					queue2.offer(new Node(r, c, 0));
				}
				if(map[r][c] == 'S') {
					queue.offer(new Node(r, c, 0));
				}
				if(map[r][c] == 'D') {
					endR = r;
					endC = c;
				}
			}	
		}
		bfs();
	}
	private static void bfs() {
		int cur = queue.peek().t;
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			if(front.r == endR && front.c == endC) {
				System.out.println(front.t);
				return;
			}

			//  물채우기
			if(front.t == cur) {
				fillWater();
				cur++;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && (map[nr][nc] == '.' || map[nr][nc] == 'D')) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.t+1));
				}
			}
		}
		System.out.println("KAKTUS");
	}
	private static void fillWater() {
		int cur = 0;
		if(!queue2.isEmpty()) {
			cur = queue2.peek().t;
		}
		while(!queue2.isEmpty()) {
			if(queue2.peek().t == cur+1) {
				return;
			}
			Node front = queue2.poll();
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && (map[nr][nc] == 'S' || map[nr][nc] == '.')) {
					queue2.offer(new Node(nr, nc, front.t+1));
					map[nr][nc] = '*';
				}
			}
		}
	}
	static class Node{
		int r;
		int c;
		int t;
		public Node(int r, int c, int t) {
			super();
			this.r = r;
			this.c = c;
			this.t = t;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", t=" + t + "]";
		}
	}
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<R && c<C);
	}
	static String src =
			"10 11\r\n" + 
			"D..........\r\n" + 
			"...........\r\n" + 
			"...........\r\n" + 
			"...........\r\n" + 
			"...........\r\n" + 
			"...........\r\n" + 
			"........S..\r\n" + 
			"...........\r\n" + 
			"...........\r\n" + 
			"...........";
}

 

 

후기

 

 생각보다 귀찮은 문제였다. 물을 채우는 방식을 더 잘 처리 해 볼수도 있을것 같다는 생각이 들지만 시간이 빠르게 나온 편이라서 그냥 두었다.

그래도 구현력(?)에 많은 도움이된 문제였다.