bfs 알고리즘 문제이다.
[백준] 14442번 : 벽 부수고 이동하기 2 - JAVA [자바]를 풀어보면 더 쉽게 풀 수 있을 것이다.
- 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
- 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
- 단, 벽은 낮에만 부술 수 있다.
위의 세가지 규칙이 생겼다.
1번 규칙을 잘 생각해보면 결국에 현재 시간이 밤이어서 다음 벽이 있는 칸에 가기 위해 낮을 기다리면서 같은 칸에 머물러 있는 경우이다.
결국에는 벽을 만났을 때 현재 시간 을 확인하는 조건을 추가하면 된다.
public static class player {
int x;
int y;
int count;
int breakWallNum;
int time;
public player(int x, int y, int count, int breakWallNum, int time) {
this.x = x;
this.y = y;
this.count = count;
this.breakWallNum = breakWallNum;
this.time = time;
}
}time 필드를 추가하여 현재 시간을 판단하였다.
// 벽이 아니면
if (map[newX][newY] != 1) {
if (!visited[newX][newY][current.breakWallNum]) {
visited[newX][newY][current.breakWallNum] = true;
queue.add(
new player(
newX, newY,
current.count + 1,
current.breakWallNum,
current.time * -1)
);
}
}-
벽이 아닌 경우
밤이든 낮이든 상관 없으며 벽을 부시는 것도 아니기 때문에 일반적인 bfs 알고리즘을 실행한다.
// 벽이면
else {
// 낮인 경우
if (current.time == 1) {
// 지금까지 부신 벽의 개수가 K 개를 안넘었을 때
if (current.breakWallNum < K) {
// 방문 여부 확인
if (!visited[newX][newY][current.breakWallNum + 1]) {
visited[newX][newY][current.breakWallNum + 1] = true;
queue.add(
new player(
newX, newY,
current.count + 1,
current.breakWallNum + 1,
current.time * -1
)
);
}
}
}
// 밤인 경우
else {
// 벽은 낮에만 부시고 이동할 수 있으므로 하루 대기
queue.add(
new player(
current.x, current.y,
current.count + 1,
current.breakWallNum,
current.time * -1
)
);
}
}-
벽인 경우
2.1 낮인 경우
- 벽을 부셔서 갈 수 있다.
- 지금까지 부순 벽의 갯수를 판단하여 부숴서 갈 수 있는지 확인
2.2 밤인 경우
- 벽을 부실 수 없다.
- 같은 칸에서 기다린다.
- 위치는 새로운 칸이 아닌 현재 위치한 칸으로 하여 큐에 삽입한다.
- 또한 문제에서 한칸 지난걸로 카운트하라 했으니 카운트는 똑같이
+ 1해준다.
주의할 점
- 한칸 움직이거나 하루를 기다리면 큐에 삽입할때 시간을 바꿔서 삽입해야 한다.
- 현재 시간이 밤이어서 같은 칸에서 기다릴 때 큐에 삽입하는 위치는 현재 위치로 삽입하여야 한다.
- 또한, 하루 대기하여도 움직인 카운트는
+ 1해줘야 한다.
public class bj16933 {
public static Queue<player> queue = new LinkedList<>();
public static int N, M, K, ANSWER = -1;
public static boolean[][][] visited;
public static int[][] map;
static int[] xMove = {1, -1, 0, 0};
static int[] yMove = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
M = Integer.parseInt(split[1]);
K = Integer.parseInt(split[2]);
map = new int[N][M];
for (int i = 0; i < N; i++) {
String line1 = br.readLine();
char[] charArray = line1.toCharArray();
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
}
}
// 낮 = 0, 밤 = 1
visited = new boolean[N][M][K + 1];
bfs(new player(0, 0, 1, 0, 1));
bw.write(ANSWER + "\n");
bw.flush();
bw.close();
br.close();
}
public static void bfs(player start) {
queue.add(start);
visited[start.x][start.y][0] = true;
while (!queue.isEmpty()) {
player current = queue.poll();
if (current.x == N - 1 && current.y == M - 1) {
ANSWER = current.count;
break;
}
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 >= N || newY >= M) continue;
// 벽이 아니면
if (map[newX][newY] != 1) {
if (!visited[newX][newY][current.breakWallNum]) {
visited[newX][newY][current.breakWallNum] = true;
queue.add(
new player(
newX, newY,
current.count + 1,
current.breakWallNum,
current.time * -1)
);
}
}
// 벽이면
else {
// 낮인 경우
if (current.time == 1) {
// 지금까지 부신 벽의 개수가 K 개를 안넘었을 때
if (current.breakWallNum < K) {
// 방문 여부 확인
if (!visited[newX][newY][current.breakWallNum + 1]) {
visited[newX][newY][current.breakWallNum + 1] = true;
queue.add(
new player(
newX, newY,
current.count + 1,
current.breakWallNum + 1,
current.time * -1)
);
}
}
}
// 밤인 경우
else {
// 벽은 낮에만 부시고 이동할 수 있으므로 하루 대기
queue.add(
new player(
current.x, current.y,
current.count + 1,
current.breakWallNum,
current.time * -1)
);
}
}
}
}
}
public static class player {
int x;
int y;
int count;
int breakWallNum;
int time;
public player(int x, int y, int count, int breakWallNum, int time) {
this.x = x;
this.y = y;
this.count = count;
this.breakWallNum = breakWallNum;
this.time = time;
}
}
}
가오리의 개발 이야기