탈출

• 큐에 물의 위치를 먼저 다 넣고 두더지의 위치를 큐에 넣는다

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int R = sc.nextInt();
		int C = sc.nextInt();
		char[][] arr = new char[R][C];

		int s_r = -1;
		int s_c = -1;

		Queue<Node> q = new LinkedList<>();
		boolean[][][] check = new boolean[2][R][C];
		for (int i = 0; i < R; i++) {
			String str = sc.next();
			for (int j = 0; j < C; j++) {
				arr[i][j] = str.charAt(j);
				if (arr[i][j] == '*') {
					q.add(new Node(i, j, 0, 0));
					check[0][i][j] = true;
				}
				if (arr[i][j] == 'S') {
					s_r = i;
					s_c = j;
				}
			}
		}

		q.add(new Node(s_r, s_c, 1, 0));

		check[1][s_r][s_c] = true;

		int re_check = -1;

		while (!q.isEmpty()) {
			Node node = q.poll();
			if (node.type == 1 && arr[node.r][node.c] == 'D') {
				re_check = node.cnt;
				break;
			}
			for (int k = 0; k < 4; k++) {
				int nr = node.r + dr[k];
				int nc = node.c + dc[k];
				if (nr < 0 || nc < 0 || nr >= R || nc >= C || check[0][nr][nc] || arr[nr][nc] == 'X')
					continue;
				if (node.type == 0) {
					if (arr[nr][nc] == 'D')
						continue;
					q.add(new Node(nr, nc, node.type, node.cnt + 1));
					check[0][nr][nc] = true;
				} else if (node.type == 1) {
					if (check[1][nr][nc])
						continue;
					q.add(new Node(nr, nc, node.type, node.cnt + 1));
					check[1][nr][nc] = true;
				}
			}
		}
		if (re_check == -1)
			System.out.println("KAKTUS");
		else
			System.out.println(re_check);

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Node {
		int r, c, type, cnt;

		Node(int r, int c, int type, int cnt) {
			this.r = r;
			this.c = c;
			this.type = type;
			this.cnt = cnt;
		}
	}
}