[백준] 2411번. 아이템 먹기(JAVA)

문제

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

---

풀이(40분)

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

public class Main {

    static int N, M, A, B;
    static int[][] map;
    static List<Point> items = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        items.add(new Point(0,0)); // 시작점 체크
        map[0][0] = 1;
        items.add(new Point(N-1, M-1)); // 종료지점 체크
        for(int i = 0; i < A; i++){ // 아이템
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            map[row][col] = 1; // 아이템은 1로 체크
            if(row == 0 && col == 0){
                continue;
            }
            if(row == N-1 && col == M-1){
                continue;
            }
            items.add(new Point(row, col));
        }

        Collections.sort(items);

        for(int i = 0; i < B; i++){ // 장애물
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            map[row][col] = -1; // 장애물은 -1로 체크
        }

        boolean flag = false; // 값에 변화가 있었는지 확인
        int answer = 1;
        for(int i = 0; i < items.size() - 1; i++){
            int count = countRoute(items.get(i), items.get(i+1)); // 두 포인트 비교
            if(count != 0){
                flag = true;
                answer *= count;
                continue;
            }
            System.out.println(0);
            return;
        }

        if(flag){
            System.out.println(answer);
            return;
        }
        System.out.println(0);
    }

    static int countRoute(Point start, Point end){
        int rowSize = end.row - start.row + 1;
        int colSize = end.col - start.col + 1;
        int[][] tempMap = new int[rowSize][colSize];
        for(int i = start.row; i <= end.row; i++){
            for(int j = start.col; j <= end.col; j++){
                tempMap[i-start.row][j-start.col] = map[i][j];
            }
        }
        tempMap[rowSize-1][colSize-1] = 0;

        for(int i = 0; i < rowSize; i++){
            for(int j = 0; j < colSize; j++){
                if(tempMap[i][j] == -1){ // 장애물이면 패스
                    continue;
                }

                if(isInBounds(i-1, j, rowSize, colSize)){ // 왼쪽에서 오는 경우
                    if(tempMap[i-1][j] != -1){ // 장애물이면 패스
                        tempMap[i][j] += tempMap[i-1][j];
                    }
                }

                if(isInBounds(i, j-1, rowSize, colSize)){ // 왼쪽에서 오는 경우
                    if(tempMap[i][j-1] != -1){ // 장애물이면 패스
                        tempMap[i][j] += tempMap[i][j-1];
                    }
                }
            }
        }

        return tempMap[rowSize-1][colSize-1];
    }

    static class Point implements Comparable<Point>{
        int row, col;

        public Point(int row, int col){
            this.row = row;
            this.col = col;
        }

        @Override
        public int compareTo(Point o){
            if(o.row != this.row){
                return this.row - o.row;
            }
            return this.col - o.col;
        }
    }

    static boolean isInBounds(int row, int col, int rowSize, int colSize){
        return row >= 0 && row < rowSize && col >= 0 && col < colSize;
    }

}

---

문제 풀이 전략

 

확률과 통계 시간에 배운 방법을 이용하면 된다.

기억이 나지 않는다면 아래 글을 참고하자. https://to-travel-coding.tistory.com/280

[백준] 1577번. 도로의 개수(JAVA)

 

그렇다면 왜 아이디어를 잘 잡아두고도 40분이나 걸린 걸까?

 

1. 시작점에 대해 list에 추가는 했어도 1이라는 값을 map에 체크해주지 않아 발생한 문제였다.

 

2. countRoute에 초기 end 좌표에 대한 값을 0으로 설정을 별도로 해주어야 했다. 

-> 그렇지 않다면 출발점->도착점으로 도착하지 못하는 경우에도 1이라는 값이 리턴될 수 있다.

 

다양한 반례를 생각하며 위의 두 가지 문제에 대해 해결하였더니 정답처리가 되었다.