[백준] 17267번 상남자

문제 설명

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

문제 풀이

• 단순 BFS 문제이다. 하지만 함정이..
• 아무 제약없이 단순히 1칸씩 움직이는 BFS 설계한 경우 92%에서 실패한다. (질문 참조)
• BFS 진행시 우선순위큐를 이용하여 남은 L, 남은 R이 많은 것 우선으로 빼주어야 예외를 제거할 수 있다. (좌, 우 진행을 최대한 늦춤)

소스 코드 (JAVA)

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static class Status implements Comparable<Status>{
        public int x, y, L, R;
        public Status(int x, int y, int l, int r) {
            this.x = x;
            this.y = y;
            L = l;
            R = r;
        }
        @Override
        public int compareTo(Status target) {
            return (L+R) <= (target.L + target.R) ? 1 : -1;
        }
    }
    public static int sX, sY, N, M, L, R, result;
    public static int[][] map = new int[1001][1001];
    public static boolean[][] chk = new boolean[1001][1001];
    public static PriorityQueue<Status> queue = new PriorityQueue<>();
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};

    public static void solve() {
        //시작 지점 체크
        result = 1;
        chk[sX][sY] = true;
        queue.add(new Status(sX, sY, L, R));
        while(!queue.isEmpty()) {
            Status curStatus = queue.poll();
            for (int d = 0; d < 4; d++) {
                int X = curStatus.x + dx[d];
                int Y = curStatus.y + dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= M || chk[X][Y] == true || map[X][Y] == 1) continue;
                //우측으로 갈 때
                if (d == 0) {
                    if (curStatus.R != 0) {
                        chk[X][Y] = true;
                        result++;
                        queue.add(new Status(X, Y, curStatus.L, curStatus.R-1));
                    }
                }
                //좌측으로 갈 때
                else if (d == 2) {
                    if (curStatus.L != 0) {
                        chk[X][Y] = true;
                        result++;
                        queue.add(new Status(X, Y, curStatus.L-1, curStatus.R));
                    }
                }
                //위, 아래로 갈 때
                else {
                    chk[X][Y] = true;
                    result++;
                    queue.add(new Status(X, Y, curStatus.L, curStatus.R));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); M = sc.nextInt(); L = sc.nextInt(); R = sc.nextInt();
        for (int i = 0; i < N; i++) {
            String input = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = Character.getNumericValue(input.charAt(j));
                if (map[i][j] == 2) {
                    sX = i; sY = j;
                    map[i][j] = 0;
                }
            }
        }
        solve();
        System.out.println(result);
    }
}