문제
https://www.acmicpc.net/problem/14923
풀이
visited 배열을 3차원으로 만들어 bfs로 풀었다. 0은 벽을 부수기 전, 1은 벽을 부순 후를 나타낸다.
코드
import java.util.*;
import java.io.*;
class Move {
int r, c, dir;
Move(int r, int c, int dir) {
this.r = r;
this.c = c;
this.dir = dir;
}
}
public class Main {
public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(in.readLine());
int Hx = Integer.parseInt(st.nextToken()) - 1;
int Hy = Integer.parseInt(st.nextToken()) - 1;
st = new StringTokenizer(in.readLine());
int Ex = Integer.parseInt(st.nextToken()) - 1;
int Ey = Integer.parseInt(st.nextToken()) - 1;
int[][] map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < M; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
boolean isPossible = false;
int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
boolean[][][] visited = new boolean[N][M][2];
Queue<Move> queue = new LinkedList<Move>();
visited[Hx][Hy][0] = true;
queue.offer(new Move(Hx, Hy, 0));
outer:
while(!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Move move = queue.poll();
if (move.r == Ex && move.c == Ey) {
isPossible = true;
break outer;
}
for (int d = 0; d < delta.length; d++) {
int dr = move.r + delta[d][0];
int dc = move.c + delta[d][1];
if (dr < 0 || dc < 0 || dr >= N || dc >= M || (map[dr][dc] == 1 && move.dir == 1))
continue;
if (!visited[dr][dc][move.dir]) {
visited[dr][dc][move.dir] = true;
queue.offer(new Move(dr, dc, map[dr][dc] == 1 ? 1 : move.dir));
}
}
}
cnt++;
}
System.out.println(isPossible ? cnt : -1);
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ 백준] 1931 - 회의실 배정, Java(자바) (0) | 2023.03.07 |
---|---|
[BOJ 백준] 12764 - 싸지방에 간 준하, Java(자바) (0) | 2023.03.07 |
[BOJ 백준] 17090 - 미로 탈출하기, Java(자바) (0) | 2023.03.04 |
[BOJ 백준] 1991 - 트리 순회, Java(자바) (0) | 2023.03.04 |
[BOJ 백준] 6068 - 시간 관리하기, Java(자바) (0) | 2023.03.03 |