문제
https://www.acmicpc.net/problem/14923
14923번: 미로 탈출
홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이
www.acmicpc.net
풀이
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 |