백준 13549번 숨바꼭질 3

문제

나의 풀이

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean c[] = new boolean[MAX];
        int d[] = new int[MAX];
        c[n] = true;
        d[n] = 0;
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
        q.add(n);
        while(!q.isEmpty()) {
            int now = q.poll();
            for(int next : new int[]{now * 2, now - 1, now + 1}) {
                if(next >= 0 && next < MAX) {
                    if(c[next] == false) {
                        c[next] = true;
                        if(next == now * 2) { // 순간이동하는 경우
                            q.addFirst(next);
                            d[next] = d[now]; // 0초 걸림
                        } else {
                            q.addLast(next);
                            d[next] = d[now] + 1; // 1초 걸림
                        }
                    }
                }
            }
        }
        System.out.println(d[m]);
    }
}

숨바꼭질 문제와 유사하나, 순간이동 할때 0초가 걸린다는 점이 다르다.
덱을 다루어서 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법을 사용하면 된다.

결과

백준 1261번 알고스팟

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();
        int a[][] = new int[n][m];
        for(int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for(int j = 0; j < m; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        
        int dx[] = { 0, 0, 1, -1 };
        int dy[] = { 1, -1, 0, 0 };
        int d[][] = new int[n][m];
        ArrayDeque<Pair> deque = new ArrayDeque<Pair>();
        deque.add(new Pair(0, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                d[i][j] = -1;
            }
        }
        
        d[0][0] = 0;
        while(!deque.isEmpty()) {
            Pair p = deque.poll();
            int x = p.x;
            int y = p.y;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if(d[nx][ny] == -1) {
                        if(a[nx][ny] == 0) { // 빈방인 경우
                            d[nx][ny] = d[x][y]; // 안 뚫기 때문에 가중치 증가 x
                            deque.addFirst(new Pair(nx, ny));
                        } else { // 벽인 경우
                            d[nx][ny] = d[x][y] + 1; // 뚫는 경우기 때문에 +1 하기
                            deque.addLast(new Pair(nx, ny));
                        }
                    } 
                }
            }
        }
        System.out.println(d[n - 1][m - 1]);
    }
}

bfs 탐색을 벽을 부순 횟수에 따라서 나누어서 수행한다.
벽을 뚫는다와 안 뚫는다로 나누어지기 때문에, 덱을 사용한다. 벽을 뚫는 경우에는 뒤에, 안 뚫는 경우에는 앞에 추가시켜서 풀면 된다.

결과