백준 3055번
https://www.acmicpc.net/problem/3055
BFS를 통해서 최단 시간을 구하면 된다.
고슴도치의 방문 여부와 물의 방문여부를 구별하는거만 생각한다면 크게 어렵지 않은 문제임
boolean[][] hedgeVisited = new boolean[R][C];
boolean[][] waterVisited = new boolean[R][C];
for (Coordinate c : waterList) {
que.offer(new Coordinate(c.x, c.y, 0, 1)); // 물
waterVisited[c.x][c.y] = true;
}
que.offer(new Coordinate(S.x, S.y, 0, 0)); // 고슴도치
hedgeVisited[S.x][S.y] = true;
고슴도치가 이동하면서 지나간 경로를 기록할 hedgeVisited
물이 이동하는 경로 waterVisited
2가지로 만들어 물은 물대로 이동하고 고슴도치는 고슴도치의 경로대로 탐색할 수 있도록 해준다.
type
은 고슴도치가 0 물이 1로 하여 어떤 값이 que
에 들어왔는지를 구분할 수 있도록 했다.
if (current.type == 0 && ableCheck(nextX, nextY, hedgeVisited) && (map[nextX][nextY] == 'D' || map[nextX][nextY] == '.')) {
que.offer(new Coordinate(nextX, nextY, current.time + 1, current.type)); // 고슴도치
hedgeVisited[nextX][nextY] = true;
} else if (current.type == 1 && ableCheck(nextX, nextY, waterVisited) && map[nextX][nextY] == '.') {
map[nextX][nextY] = '*';
que.offer(new Coordinate(nextX, nextY, current.time, current.type));
waterVisited[nextX][nextY] = true;
}
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static final String FAIL = "KAKTUS";
private static int R, C;
private static char[][] map;
private static Coordinate D, S;
private static List<Coordinate> waterList;
private static final int[] dirX = {0, 0, -1, 1};
private static final int[] dirY = {-1, 1, 0, 0};
private static class Coordinate {
int x;
int y;
int time;
int type;
private Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
private Coordinate(int x, int y, int time, int type) {
this.x = x;
this.y = y;
this.time = time;
this.type = type;
}
} // End of Coordinate class
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
int ret = BFS();
if (ret == -1) {
sb.append(FAIL);
} else {
sb.append(ret);
}
return sb.toString();
} // End of solve()
private static int BFS() {
LinkedList<Coordinate> que = new LinkedList<>();
boolean[][] hedgeVisited = new boolean[R][C];
boolean[][] waterVisited = new boolean[R][C];
for (Coordinate c : waterList) {
que.offer(new Coordinate(c.x, c.y, 0, 1)); // 물
waterVisited[c.x][c.y] = true;
}
que.offer(new Coordinate(S.x, S.y, 0, 0)); // 고슴도치
hedgeVisited[S.x][S.y] = true;
while (!que.isEmpty()) {
Coordinate current = que.poll();
if (current.x == D.x && current.y == D.y && current.type == 0) {
return current.time;
}
for (int i = 0; i < 4; i++) {
int nextX = dirX[i] + current.x;
int nextY = dirY[i] + current.y;
if (current.type == 0 && ableCheck(nextX, nextY, hedgeVisited) && (map[nextX][nextY] == 'D' || map[nextX][nextY] == '.')) {
que.offer(new Coordinate(nextX, nextY, current.time + 1, current.type)); // 고슴도치
hedgeVisited[nextX][nextY] = true;
} else if (current.type == 1 && ableCheck(nextX, nextY, waterVisited) && map[nextX][nextY] == '.') {
map[nextX][nextY] = '*';
que.offer(new Coordinate(nextX, nextY, current.time, current.type));
waterVisited[nextX][nextY] = true;
}
}
}
return -1;
} // End of BFS()
private static boolean ableCheck(int nextX, int nextY, boolean[][] visited) {
return nextX >= 0 && nextX < R && nextY >= 0 && nextY < C && !visited[nextX][nextY];
} // End of ableCheck()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
waterList = new ArrayList<>();
for (int i = 0; i < R; i++) {
String temp = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = temp.charAt(j);
if (map[i][j] == 'D') {
D = new Coordinate(i, j);
} else if (map[i][j] == 'S') {
S = new Coordinate(i, j);
map[i][j] = '.';
} else if (map[i][j] == '*') {
waterList.add(new Coordinate(i, j));
}
}
}
} // End of input()
} // End of Main class