[백준 3055] 게임- 탈출(solved.ac - 골드 4)

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

3055번: 탈출

풀이

문제를 보았을 때 알 수 있는 힌트

간단한 BFS문제에 홍수가 추가된 문제이다. 처음에는 어떻게 접근을 해야하는지 조차 이해를 못해서 다른사람들이 코드를 보았다.

다른 사람들의 코드를 보니 홍수를 한번 움직이고 이후 고슴도치를 움직이게 하며, 그때 고슴도치 움직인 위치는 홍수가 와도 결국에 움직일수 있기에 무시하는 형식으로 코드가 작성되어있었다.

나역시 이를 참고하여 문제를 풀었다.

 

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

public class Main {
	// baekjoon 3055
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static Queue<int[]> q = new LinkedList<>();
	static Queue<int[]> water = new LinkedList<>();
	static Character[][] map;
	static int[][] count;
	static int r, c;
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		map = new Character[r][c];
		count = new int[r][c];

		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'S') {
					q.add(new int[] { i, j, 0 });
				} else if (map[i][j] == '*') {
					water.add(new int[] { i, j });
				}
			}
		}
		bfs();
		System.out.println(answer == Integer.MAX_VALUE?"KAKTUS":answer);
		
	}
	
	public static void bfs() {
		while(!q.isEmpty()) {
			int len = water.size();
			for(int i=0;i<len;i++) {
				int[] t = water.poll();
				int x = t[0];
				int y = t[1];
				for(int k=0;k<4;k++) {
					int nx = x+dx[k];
					int ny = y+dy[k];
					if(0<=nx && nx<r && 0<=ny && ny<c && map[nx][ny]=='.') {
						map[nx][ny] = '*';
						water.add(new int[] {nx,ny});
					}
				}
			}
			
			// 고슴도치 이동
			len = q.size();
			for(int i=0;i<len;i++) {
				int[] t = q.poll();
				int x = t[0];
				int y = t[1];
				int time = t[2];
				for(int k = 0;k<4;k++) {
					int nx = x+dx[k];
					int ny = y+dy[k];
					if(0<=nx && nx<r && 0<=ny && ny<c) {
						if(map[nx][ny]=='D') {
							//정답!
							answer = Math.min(answer,time+1);
							return;
						}
						else if(map[nx][ny]=='.') {
							map[nx][ny] = 'S';
							q.add(new int[] {nx,ny,time+1});
						}
					}
				}
			}
			
		}
	}

}

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/java/baekjoon3055/Main.java

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리