반응형
11-15 01:35
Today
Total
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
관리 메뉴

개발하는 고라니

[백준] 14923번 : 미로 탈출 본문

Programming/백준

[백준] 14923번 : 미로 탈출

조용한고라니 2021. 4. 15. 01:21
반응형
 

14923번: 미로 탈출

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이

www.acmicpc.net


[BFS]

아마 기억 상 '벽 부수고 이동하기 1' 문제와 90% 유사한 문제 같다.

 

[백준] 2206번 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하

dev-gorany.tistory.com

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));
    }
}
반응형
Comments