[Java] SWEA 오! 나의 여신님

1. 문제 분석

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG 

SW Expert Academy

백준에서 불! 과 같은 문제다. BFS 문제로 1초마다 수연이는 한칸씩, 부식되는 곳 또한 계속 상하좌우로 한칸씩 움직인다.

필자는 수연이가 움직이는 큐, 부식되는 큐로 나누어서 풀었다.

주의할 점은 1초마다 부식되는 것으로 모든 큐를 싹 뽑아서 부식을 체크하고 큐에 넣는 식으로 해야한다.

2. 구현

package samsung01;

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

class Point {
	int x, y, dist;

	Point(int x, int y, int dist) {
		this.x = x;
		this.y = y;
		this.dist = dist;
	}
}

public class Solution {

	static char[][] map;
	static int N, M;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int min = Integer.MAX_VALUE;
	static ArrayList<Point> dList = new ArrayList<>();
	static boolean[][] sVisited;
	static boolean[][] dVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		for (int c = 1; c <= tc; c++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			int startX = 0, startY = 0;

			map = new char[N][M];
			sVisited = new boolean[N][M];
			dVisited = new boolean[N][M];

			for (int i = 0; i < N; i++) {
				char[] inputData = br.readLine().toCharArray();
				for (int j = 0; j < M; j++) {
					char input = inputData[j];
					if (input == 'S') {
						startX = j;
						startY = i;
					} else if (input == '*') {
						dList.add(new Point(j,i, 0));
					}
					map[i][j] = input;
				}
			}
			bfs(startX, startY, dList);

			if (min == Integer.MAX_VALUE)
				System.out.println("#" + c + " " + "GAME OVER");
			else
				System.out.println("#" + c + " " + min);

			min = Integer.MAX_VALUE;
			dList.clear();
		}
	}

	static void bfs(int startX, int startY, ArrayList<Point> dList) {
		Queue<Point> sQueue = new LinkedList<>();
		Queue<Point> dQueue = new LinkedList<>();

		sQueue.offer(new Point(startX, startY, 0));
		for(Point d : dList) {
			dQueue.offer(d);
			dVisited[d.y][d.x] = true;
		}
		sVisited[startY][startX] = true;

		while (!sQueue.isEmpty() || !dQueue.isEmpty()) {

			if (!dQueue.isEmpty()) {
				int dSize = dQueue.size();
				for (int j = 0; j < dSize; j++) {
					Point dp = dQueue.poll();
					for (int i = 0; i < 4; i++) {
						int mx = dp.x + dx[i];
						int my = dp.y + dy[i];
						int dist = dp.dist;

						if (mx < 0 || my < 0 || mx >= M || my >= N)
							continue;
						if (dVisited[my][mx] || map[my][mx] == 'D' || map[my][mx] == 'X')
							continue;
						dVisited[my][mx] = true;
						dQueue.offer(new Point(mx, my, dist + 1));
					}
				}
			}
			if (!sQueue.isEmpty()) {
				int sSize = sQueue.size();
				for (int j = 0; j < sSize; j++) {
					Point sp = sQueue.poll();

					if (map[sp.y][sp.x] == 'D') {
						min = Math.min(sp.dist, min);
						break;
					}

					for (int i = 0; i < 4; i++) {
						int mx = sp.x + dx[i];
						int my = sp.y + dy[i];
						int dist = sp.dist;

						if (mx < 0 || my < 0 || mx >= M || my >= N)
							continue;
						if (dVisited[my][mx] || sVisited[my][mx] || map[my][mx] == '*' || map[my][mx] == 'X')
							continue;

						sVisited[my][mx] = true;
						sQueue.offer(new Point(mx, my, dist + 1));
					}
				}
			}
		}
	}
}

3. 마무리

BFS는 이제 눈에 딱 보인다.. 응용 문제를 풀어야 할 것 같다.