백준 16933: java

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

16933번: 벽 부수고 이동하기 3

벽 부수고 이동하기 3

아이디어

BFS 너비우선 탐색을 활용한다. 이때 현재위치, 내가 뿌순 벽수, 낮과밤 을 이용해서 풀수있다.
낮과밤은 홀수짝수 개념으로 0 : 낮 1 : 밤으로 하고 1을 더하고 %2 한것은 항상 0과 1를 이용해서 풀수있다.

visit 배열말 잘선언해주고 조건에 맞게 BFS 탐새을 이용하면 쉽게 풀수있다.
BFS 탐색시 q.size 만큼 만 poll을 해서 사용하면 하나의 사이클이 time이 하나증가하는 것을 알 수 있다.

 

package algo;
 
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 B16933 {
    static int N, M, K;
    static int dy[] = { 0, 0, 1, -1 };
    static int dx[] = { 1, -1, 0, 0 };
    static char map[][];
    static boolean visit[][][][];
 
    static class Pair {
        int y;
        int x;
        int k;
        int dayNight;
 
        public Pair(int y, int x, int k, int dayNight) {
            super();
            this.y = y;
            this.x = x;
            this.k = k;
            this.dayNight = dayNight;
        }
    }
 
    static boolean rangeCheck(int y, int x) {
        if (y < 0 || x < 0 || y >= N || x >= M)
            return false;
        return true;
    }
 
    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());
        K = Integer.parseInt(st.nextToken());
 
        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }
        visit = new boolean[N][M][K + 1][2];
 
        visit[0][0][0][0] = true;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0, 0, 0));
        int ans = -1;
        int time = 1;
 
        while (!q.isEmpty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                Pair cur = q.poll();
                if (cur.y == N - 1 && cur.x == M - 1) {
                    ans = time;
                    break;
                }
                // 가만히 있기
                if (!visit[cur.y][cur.x][cur.k][(cur.dayNight + 1) % 2]) {
                    visit[cur.y][cur.x][cur.k][(cur.dayNight + 1) % 2] = true;
                    q.add(new Pair(cur.y, cur.x, cur.k, (cur.dayNight + 1) % 2));
                }
 
                // 이동하기
                for (int d = 0; d < 4; d++) {
                    int ny = cur.y + dy[d];
                    int nx = cur.x + dx[d];
                    if (rangeCheck(ny, nx)) {
 
                        if (map[ny][nx] == '1' && cur.dayNight == 0) {
                            if (cur.k == K)
                                continue;
                            if (!visit[ny][nx][cur.k + 1][1]) {
                                visit[ny][nx][cur.k + 1][1] = true;
                                q.add(new Pair(ny, nx, cur.k + 1, 1));
                            }
                        } else if (map[ny][nx] == '0') {
                            if (!visit[ny][nx][cur.k][(cur.dayNight + 1) % 2]) {
                                visit[ny][nx][cur.k][(cur.dayNight + 1) % 2] = true;
                                q.add(new Pair(ny, nx, cur.k, (cur.dayNight + 1) % 2));
                            }
                        }
                    }
                }
 
            }
 
            if (ans != -1) {
                break;
            }
 
            time++;
        }
        System.out.println(ans);
    }
}