백준 1584 게임 - BFS

시작점, 끝점이 주어질때 끝점으로 이동하면서 주어진 조건에 따라 최소값 또는 최댓값을 구하는 전형적인 BFS 문제이다.

시작점 : 0,0
끝점 : 500,500

문제의 조건 : 영역에 따라 0 또는 1을 더 하고 갈수 없는 지역이 존재

놓친점 1

다음 영역에 대한 비용 Cost를 계산할때 안에 넣는 변수를 실수하지 않고 넣어줘야 한다. 현재지역변수와 다음지역변수를 헷갈리지 않아야한다.

예를들어 해당 문제에서는, 현재지역비용 + 다음지역으로 추가되는 비용 = 새로운 비용
식이 존재하는데 예를들면 이런실수를 하지 않도록 항상 "새로운 비용을 계산할떄는 2번확인하기"

// 새로운 비용 = 현재비용 + 다음지역 이동비용 (정상)
int newCost = value[cur.x][cur.y] + board[nx][ny];

// 새로운 비용 = 현재비용 + 현재지역 이동비용 (비정상) -> 코테망함
int newCost = value[cur.x][cur.y] + board[cur.x][cur.y];

놓친점 2

처음에 BFS로 접근해야지 하고 DFS로 작성하고 있었다.
DFS의 경우 하나의 점에서 길 별로 500 * 500번 반복하게되므로 메모리가 남아나지 않게된다.

패턴이 일정해서 암기로 많이 외우고 코테때 빠르게 넘어가 시간을 많이 확보해야하는 유형이다.

코드

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

public class Main {

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int[][] board ;
    static int[][] value;
    public static void main(String[] args) throws IOException {

        board = new int[501][501];
        value = new int[501][501];
        for (int i = 0; i < 501; i++) {
            for (int j = 0; j < 501; j++) {
                value[i][j]= Integer.MAX_VALUE;
            }
        }
        value[0][0]=0;
        // init 필요 0,0 제외

        // 위험지역
        int N = Integer.parseInt(br.readLine());
        setBoard(N, board, 1);

        // 금지지역
        int M = Integer.parseInt(br.readLine());
        setBoard(M,board,2);


        board[0][0]=0;

        bfs(0,0);

        if (value[500][500]==Integer.MAX_VALUE){
            System.out.println(-1);
        }
        else {
            System.out.println(value[500][500]);
        }
    }

    public static void bfs(int startX, int startY){
        Queue<Node> queue = new LinkedList<>();

        queue.add(new Node(startX,startY));
        while (!queue.isEmpty()){
            Node cur = queue.poll();

            int[] dy = {1,-1,0,0};
            int[] dx = {0,0,1,-1};

            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + cur.y;
                int nx = dx[i] + cur.x;

                if (nx < 0 || nx > 500 || ny <0 || ny > 500){
                    continue;
                }

                if (board[nx][ny]==2){
                    continue;
                }


                // 현재 밸류 + 1
                int newCost = value[cur.x][cur.y] + board[nx][ny];

                if (value[nx][ny] > newCost){
                    value[nx][ny] = newCost; // 더 작은거
                    queue.add(new Node(nx,ny));
                }
            }
        }
    }

    private static void setBoard(int N, int[][] board, int fill) throws IOException {
        for (int i = 0; i < N; i++) {
            String[] inp = br.readLine().split(" ");

            int x1 = Integer.parseInt(inp[0]);
            int y1 = Integer.parseInt(inp[1]);
            int x2 = Integer.parseInt(inp[2]);
            int y2 = Integer.parseInt(inp[3]);

            // 항상 x1 y1이 작도록 변경
            if (x1 > x2 ){
                int tmp = x1;
                x1 = x2;
                x2 = tmp;
            }
            if (y1 > y2){
                int tmp = y1;
                y1 = y2;
                y2 = tmp;
            }

            for (int x = x1; x <= x2; x++){
                for (int y = y1; y <= y2; y++){
                    board[x][y] = fill;
                }
            }
        }
    }

}