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

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

분류 : BFS

 

import java.io.*;
import java.math.*;
import java.util.*;

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    public Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static Myscanner sc = new Myscanner();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int N, M, inf = Integer.MAX_VALUE / 2;
    static char[][] adj;
    static int[][][] map;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    public static void main(String[] args) throws IOException {

        N = sc.nextInt();
        M = sc.nextInt();
        adj = new char[N + 1][M + 1];
        map = new int[N + 1][M + 1][2];

        for (int i = 1; i <= N; i++) {
            String str = sc.next();
            for (int j = 1; j <= M; j++) {
                adj[i][j] = str.charAt(j - 1);
            }
        }
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                for (int k = 0; k <= 1; k++)
                    map[i][j][k] = inf;

        Queue<Point> q = new LinkedList<>();
        map[1][1][0] = 1;
        q.offer(new Point(1, 1, 0));

        while (!q.isEmpty()) {
            int size = q.size();
            for (int sz = 0; sz < size; sz++) {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                int check = p.check;
                for (int ar = 0; ar < 4; ar++) {
                    int cx = x + dx[ar];
                    int cy = y + dy[ar];

                    if (cx >= 1 && cx <= N && cy >= 1 && cy <= M) {
                        if (adj[cx][cy] == '0' && (map[cx][cy][check] > map[x][y][check] + 1)) {
                            map[cx][cy][check] = map[x][y][check] + 1;
                            q.offer(new Point(cx, cy, check));
                        } else if (adj[cx][cy] == '1' && check == 0 && (map[cx][cy][check] > map[x][y][check] + 1)) {
                            map[cx][cy][1] = map[x][y][0] + 1;
                            q.offer((new Point(cx, cy, 1)));
                        }
                    }
                }
            }
        }
        if (map[N][M][0] == inf && map[N][M][1] == inf)
            out.println(-1);
        else
            out.println(Math.min(map[N][M][0], map[N][M][1]));
        out.flush();
    }
}

class Point {
    int x;
    int y;
    int check;

    Point(int x, int y, int check) {
        this.x = x;
        this.y = y;
        this.check = check;
    }
}

 

미로 문제나 탈출 하는 BFS 문제가 제일 재밌는 것 같다..

이 문제는 벽을 부수냐 마냐 의 경우를 추가해서 BFS를 돌려서 풀면 된다.

앞으로 더 열심히 많이 풀어야지