1106번 : 호텔 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (33분 20초)

아이디어

이 문제는 일단 BFS로 풀면 간단하게 풀릴 수 있는 문제이다.
그런데 처음에 단순 최단거리를 구하는 것이 아니기에 DFS로 해볼까 하다가
최악의 경우인 20마을 전체에 C는 1000이고 각 마을에는 고객이 한명씩만 존재한다는 가정에서는
수많은 재귀호출이 발생할 것이라는 생각을 하였고 DP또는 BFS로 하면 되겠다고 생각이 들었다.

문제에서 정수 배수만큼 한꺼번에 처리할 수 있다는 그런 말이 있는데
여기서 오해하면 안되는 것이 한번에 최대로 고객 끌어올 수 있을 만큼만 처리하면
올바른 결과가 결코 나오지 않는다. 그래서 나는 무조건 1배수로 광고를 하기로 했다.

일단 BFS 동작에서의 핵심은 이렇다.

1. 방문처리 -> visited[고객 수] = 비용 저장
2. C를 초과하는 것도 성공했다고 봐야함 -> 이번 연산의 customer수가 C이상이면 결과 비교 후 저장

정답 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        ArrayList<int []> info = new ArrayList<>();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            info.add(new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
        }
        ArrayDeque<int []> q = new ArrayDeque<>();
        int [] visited = new int[C+1002];
        Arrays.fill(visited, Integer.MAX_VALUE);
        q.add(new int[]{0, 0});// 비용, 고객 수
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int cost = cur[0];
            int customer = cur[1];
            if(customer>=C){
                visited[C] = Math.min(cost, visited[C]);
                continue;
            }
            for (int [] x: info){
                int dx = x[0]+cost;
                int dy = x[1]+customer;
                if(dy<=C+1001 && visited[dy]>dx){
                    visited[dy] = dx;
                    q.add(new int []{dx, dy});
                }
            }
        }
        System.out.print(visited[C]);
    }
}