[자바] 백준 1584 - 게임 (java)

목차

문제 : boj1584

 

 

필요 알고리즘

• 0-1 너비 우선 탐색 (0-1 bfs), 다익스트라 (dijkstra)
  
  • 간선이 0 또는 1일 경우에 대한 문제이다. 다익스트라로도 풀 수 있고, 0-1 bfs를 쓰면 더 효율적으로 가능하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  맵의 각 지점의 상태는 안전, 위험, 죽음 이다. 죽음은 아예 안가면 되므로 딱히 상관없다. 안전과 위험만 보면 되는데, 안전은 가중치가 0인 셈이고 위험은 1인 셈이다. 배열을 그래프라고 생각해보면 결국 가중치가 0 또는 1인 간선들을 지나갈 때 (0,0)에서 (500,500)으로의 최단 경로를 구하는 문제이다.

 

  이 때 위험이나 죽음 구역이 정점 1개씩이 아니라 여러개가 한꺼번에 입력으로 들어와서 어떻게 처리해야할지 잘 모를 수 있다. 전체 맵의 크기가 500x500이고, N+M의 최대치는 100이므로 O(100*500*500) = O(25,000,000) 이라 그냥 별다른 생각 없이 직접 맵에 기록해도 상관 없다.

private void marking(int[][] arr, int x1, int y1, int x2, int y2, int mark) {
    int xs = x1<x2?x1:x2;
    int xe = x1<x2?x2:x1;
    int ys = y1<y2?y1:y2;
    int ye = y1<y2?y2:y1;

    for (int i = xs; i <= xe; i++) {
        for (int j = ys; j <= ye; j++) {
            arr[i][j] = mark;
        }
    }
}

 

  그럼 이제 진행 불가한 위치(죽음 구역)와, 가중치(안전, 위험 구역)가 모두 정해졌으니 다익스트라 혹은 0-1 bfs를 돌리면 답을 구할 수 있다. 내 경우엔 0-1 bfs로 진행했다.

while (!dq.isEmpty()) {
    int[] cur = dq.pollFirst();
    int x = cur[0];
    int y = cur[1];
    int curDist = cur[2];

    for (int d = 0; d < 4; d++) {
        int nr = x+DR[d];
        int nc = y+DC[d];

        if (nr>500||nr<0||nc>500||nc<0||arr[nr][nc]==DEATH) continue;
        if (dist[nr][nc] <= curDist + arr[nr][nc]) continue;

        dist[nr][nc] = curDist + arr[nr][nc];
        if (arr[nr][nc] == 0) dq.addFirst(new int[] {nr, nc, curDist});
        else dq.addLast(new int[] {nr, nc, curDist+1});
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int[] DR = {1, 0, 0, -1};
    private static final int[] DC = {0, 1, -1, 0};
    private static final int WARNING = 1;
    private static final int DEATH = 2;
    private static final int INF = 250001;


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int[][] arr = new int[501][501];

        int n = Integer.parseInt(br.readLine());
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            marking(arr, x1, y1, x2, y2, WARNING);
        }

        int m = Integer.parseInt(br.readLine());
        while (m-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            marking(arr, x1, y1, x2, y2, DEATH);
        }

        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(new int[]{0,0,0});
        int[][] dist = new int[501][501];
        for (int[] row : dist) Arrays.fill(row, INF);
        dist[0][0] = 0;

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0];
            int y = cur[1];
            int curDist = cur[2];

            for (int d = 0; d < 4; d++) {
                int nr = x+DR[d];
                int nc = y+DC[d];

                if (nr>500||nr<0||nc>500||nc<0||arr[nr][nc]==DEATH) continue;
                if (dist[nr][nc] <= curDist + arr[nr][nc]) continue;

                dist[nr][nc] = curDist + arr[nr][nc];
                if (arr[nr][nc] == 0) dq.addFirst(new int[] {nr, nc, curDist});
                else dq.addLast(new int[] {nr, nc, curDist+1});
            }
        }

        System.out.println(dist[500][500] == INF ? -1 : dist[500][500]);
    }

    private void marking(int[][] arr, int x1, int y1, int x2, int y2, int mark) {
        int xs = x1<x2?x1:x2;
        int xe = x1<x2?x2:x1;
        int ys = y1<y2?y1:y2;
        int ye = y1<y2?y2:y1;

        for (int i = xs; i <= xe; i++) {
            for (int j = ys; j <= ye; j++) {
                arr[i][j] = mark;
            }
        }
    }
}