bfs 알고리즘 문제이다.
- 고슴도치
S가 비버 소굴D로 가는 최단 거리를 구한다. - 경로 중 물에 닿으면 안된다.
- 1분마다 물이 인접한 곳으로 퍼진다.
static Queue<point> queue = new LinkedList<>();
static Queue<point> waterQueue = new LinkedList<>();먼저 고슴도치의 경로를 탐색할 Queue 와 물이 퍼지는 경로를 탐색할 WaterQueue 두 개를 정의한다.
static int[] xMove = {1, -1, 0, 0};
static int[] yMove = {0, 0, -1, 1};상하좌우를 탐색하기 위한 배열을 정의한다.
// 고슴도치 경로 탐색 bfs
public static void bfs(point end, point start) {
queue.add(start);
visited[start.x][start.y] = true;
while (!queue.isEmpty()) {
// 다음 1분 동안 움직일 수 있는 경로를 탐색하기 위해
// 현재 큐에 담긴 수 만큼만 반복하여 경로를 탐색한 뒤
// 1분을 경과해 물의 이동을 적용한다.
int sameMinutes = queue.size();
for (int s = 0; s < sameMinutes; s++) {
point current = queue.poll();
// 만약 지금 경로가 물에 잠긴다면 건너뛴다.
if (map[current.x][current.y] == '*') continue;
// 상하좌우 탐색
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
// 유효한 범위 내의 움직임인지
if (newX < 0 || newY < 0 || newX >= R || newY >= C) continue;
// 도착
if (newX == end.x && newY == end.y) {
ANSWER = "" + (current.count + 1);
return;
}
// 이동할 곳이 돌이거나 물이 아니면 이동
if (map[newX][newY] != 'X' && map[newX][newY] != '*') {
if (!visited[newX][newY]) {
visited[newX][newY] = true;
queue.add(new point(newX, newY, current.count + 1));
}
}
}
}
// 1분 지남 물 움직임
waterFlow();
}
}앞으로 1분 동안 움직일 수 있는 경로를 탐색한 뒤에는 1분이 경과해 물이 퍼지므로 현재 큐에 담긴 수만큼만 탐색하면 앞으로 1분동안 움직일 수 있는 경로에 대해서만 탐색할 수 있다.
// 1분이 경과해 물이 움직임
public static void waterFlow() {
// 물도 1분 동안만 탐색할 것이므로
int sameMinutes = waterQueue.size();
for (int s = 0; s < sameMinutes; s++) {
point current = waterQueue.poll();
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
if (newX < 0 || newY < 0 || newX >= R || newY >= C) continue;
// 이동할 곳이 돌이나 비버 소굴이 아니면 물이 참
if (map[newX][newY] != 'X' && map[newX][newY] != 'D') {
if (!waterVisited[newX][newY]) {
map[newX][newY] = '*';
waterVisited[newX][newY] = true;
waterQueue.add(new point(newX, newY, 0));
}
}
}
}
}public class bj3055 {
static Queue<point> queue = new LinkedList<>();
static Queue<point> waterQueue = new LinkedList<>();
static String ANSWER = "KAKTUS";
static char[][] map;
static boolean[][] visited, waterVisited;
static int[] xMove = {1, -1, 0, 0};
static int[] yMove = {0, 0, -1, 1};
static int R, C;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
R = Integer.parseInt(split[0]);
C = Integer.parseInt(split[1]);
map = new char[R][C];
visited = new boolean[R][C];
waterVisited = new boolean[R][C];
point D = null, S = null, water = null;
for (int i = 0; i < R; i++) {
char[] charArray = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
map[i][j] = charArray[j];
if (map[i][j] == 'D') {
D = new point(i, j, 0);
} else if (map[i][j] == 'S') {
S = new point(i, j, 0);
} else if (map[i][j] == '*') {
water = new point(i, j, 0);
waterQueue.add(water);
}
}
}
bfs(D, S);
System.out.println(ANSWER);
br.close();
}
public static void bfs(point end, point start) {
queue.add(start);
visited[start.x][start.y] = true;
while (!queue.isEmpty()) {
int sameMinutes = queue.size();
for (int s = 0; s < sameMinutes; s++) {
point current = queue.poll();
if (map[current.x][current.y] == '*') continue;
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
if (newX < 0 || newY < 0 || newX >= R || newY >= C) continue;
// 도착
if (newX == end.x && newY == end.y) {
ANSWER = "" + (current.count + 1);
return;
}
// 이동할 곳이 돌이거나 물이 아니면 이동
if (map[newX][newY] != 'X' && map[newX][newY] != '*') {
if (!visited[newX][newY]) {
visited[newX][newY] = true;
queue.add(new point(newX, newY, current.count + 1));
}
}
}
}
// 1분 지남 물 움직임
waterFlow();
}
}
public static void waterFlow() {
int sameMinutes = waterQueue.size();
for (int s = 0; s < sameMinutes; s++) {
point current = waterQueue.poll();
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
if (newX < 0 || newY < 0 || newX >= R || newY >= C) continue;
// 이동할 곳이 돌이 아니면 물이 참
if (map[newX][newY] != 'X' && map[newX][newY] != 'D') {
if (!waterVisited[newX][newY]) {
map[newX][newY] = '*';
waterVisited[newX][newY] = true;
waterQueue.add(new point(newX, newY, 0));
}
}
}
}
}
public static class point {
int x;
int y;
int count;
public point(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
}
가오리의 개발 이야기