반응형
11-15 01:35
- Today
- Total
Link
개발하는 고라니
[백준] 14923번 : 미로 탈출 본문
반응형
[BFS]
아마 기억 상 '벽 부수고 이동하기 1' 문제와 90% 유사한 문제 같다.
BFS를 수행할 때 Queue안에 들어가는 원소는 4개이다.
[ (y, x)좌표, 이동한 수, 벽을 몇 개 부수었는지 ]
BFS의 로직은 다음과 같다.
1. 다음 방문할 정점이 0일 때
- 이동
2. 다음 방문할 정점이 1일 때
- 현재 벽을 부순 개수가 0개 일 때
- 벽을 부수고 이동
- 현재 벽을 부순 개수가 1개 일 때
- skip
이를 visit[1001][1001][2]를 사용해 처리했다. 마지막에 [2]가 벽을 부순 개수이다.
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point{
int y, x, d, wall;
public Point(int yy, int xx, int dist, int wall){
y=yy;
x=xx;
d=dist;
this.wall = wall;
}
}
static int n, m;
static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
static int[][] map = new int[1001][1001];
static boolean[][][] visit = new boolean[1001][1001][2];
static int BFS(int sy, int sx, int ey, int ex){
Queue<Point> Q = new LinkedList<>();
visit[sy][sx][0] = true;
Q.add(new Point(sy, sx, 0, 0));
while(!Q.isEmpty()){
Point p = Q.poll();
int y = p.y;
int x = p.x;
int dist = p.d;
int wall = p.wall;
if(y == ey && x == ex)
return dist;
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx][wall]) continue;
if(map[ny][nx] == 1){
if(wall > 0) continue;
else{
visit[ny][nx][1] = true;
Q.add(new Point(ny, nx, dist + 1, 1));
}
}
else{
visit[ny][nx][wall] = true;
Q.add(new Point(ny, nx, dist + 1, wall));
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int sY = Integer.parseInt(st.nextToken());
int sX = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int eY = Integer.parseInt(st.nextToken());
int eX = Integer.parseInt(st.nextToken());
for(int i=1; i<=n; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=m; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(BFS(sY, sX, eY, eX));
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 16932번 : 모양 만들기 (0) | 2021.04.15 |
---|---|
[백준] 16973번 : 직사각형 탈출 (0) | 2021.04.15 |
[백준] 18119번 : 단어 암기 (0) | 2021.04.09 |
[백준] 16947번 : 서울 지하철 2호선 (0) | 2021.04.08 |
[백준] 16933번 : 벽 부수고 이동하기 3 (0) | 2021.04.08 |
Comments