[ Baekjoon - 09/19 ] - 1005번: ACM Craft

• 문제 링크 : https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

• 소요 시간 : 1시간 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     • 테스트 케이스 수 T개(T>0), 건물개수 N(2<N≤1000), 건물 세울 때 규칙의 개수 K(1≤K≤100,000)
     • i번 건물이 건설에 걸리는시간 Di (0≤Di≤100,000), 건물번호 X와 Y, W(1≤X,Y, W≤N)
     • W를 건설완료하기까지 걸리는 시간을 출력하는 문제
     • 다만 건물 규칙에 따라 어떤건물이 세워져야 다른 건물을 세울수 있는 경우가 있으므로 이를 잘 고려해야함. 
   • 이해
     • 위 문제는 사실 문제 이해를 못하겠다기보다는, 입력으로 받는 변수들이 바로 와닿지가 않아서 2번과정을 통해 입력부분을 나열해보며 이해했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입력부분들을 형식에 맞게 나열해보았고, 문제에서 들어준 예시를 직접 다시 그려보았다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 우선 예시도 보면 그래프 형태로 나타나 있으므로, 형태를 간선리스트, 인접행렬, 인접리스트 중 어떻게 나타낼 것인지 생각해보았다.
     * 인접행렬 : 노드(건물)의 수는 2이상 1000이하 이므로 이차원배열로 나타내기엔 너무 공간차지가 크다 - 기각
     * 간선 리스트 : 공간차지가 덜하지만, 건물번호를 알고있을때 바로 접근하기가 용이하지 않아서 불필요한 계산을 필요로 한다 - 기각
     * 인접 리스트 : 공간차지도 덜하고, 몇번노드에서 출발한 간선들의 정보를 바로 접근하기 용이하므로 채택
     
   • 이제 이를 DFS나 BFS로 탐색해야하는데, BFS로도 충분히 탐색이 가능할 것 같아 채택했다. 
4. 위 계획을 검증
   • 인접리스트로 택한이유는 위에 언급했고, 사실상 검증과 유사한 과정이니 생략하겠음
   • BFS가 가능한 이유
     => BFS의 절차는 크게 아래와 같이 6가지로 볼 수 있다

     • 

     • 위 각 수행문에 대해 어떤일이 있을 때 분기처리를 해줘야하는지 분석해보겠다.
       1. 큐에서 꺼내옴
       2. 목적지인가 - 위 문제에서는 필요없다
       3. 연결된 곳을 순회
          • 해당 건물번호에 연결된 건물들은 인접리스트형태로 바로 찾아갈 수 있었다
          • 즉, n번째 건물이면 n번째 인접리스트는 n을 시작점으로 했을때 목적지를 가진 리스트이다.
          • 이를 순회하면 된다.
       4. 갈수있는가
          • 각 인덱스별 간선의 크기(차수)를 보관하는 변수를 선언했을때(in이라 하자) 연결된곳을 모두 순회하면 차수가 0 이 되므로, 차수가 0일때 처리해주면 된다. 
       5. 체크인 - 위 문제에서 필요없다
       6. 큐에넣음
5. 계획 수행 (실제코드 작성) - 언어는 다르지만, 흐름은 같다.
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int T,N,K,W;
            static List<Integer> timeToConstruct;
            static List<Integer>[] adjList;
            static int[] in;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
        
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                T = Integer.parseInt(br.readLine());
                while (T-- > 0) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    N = Integer.parseInt(st.nextToken());
                    K = Integer.parseInt(st.nextToken());
                    timeToConstruct = new ArrayList<>();
        
                    st = new StringTokenizer(br.readLine());
                    for (int n = 1; n < N+1; n++) {
                        timeToConstruct.add(Integer.parseInt(st.nextToken()));
                    }
        
                    in = new int[N+1];
                    adjList = new ArrayList[N+1];
                    for(int i = 0; i < N+1; i++) {
                        adjList[i] = new ArrayList();
                    }
        
                    for (int k = 0; k < K; k++) {
                        st = new StringTokenizer(br.readLine());
                        int from = Integer.parseInt(st.nextToken());
                        int to = Integer.parseInt(st.nextToken());
                        adjList[from].add(to);
                        in[to]++;
                    }
        
                    W = Integer.parseInt(br.readLine());
        
                    //System.out.println(Arrays.toString(adjList));
                    BFS(in, W);
                }
            }
        
            private static void BFS(int[] in, int destination) {
                Queue<Integer> q = new LinkedList();
                int[] result = new int[N+1]; //누적된 시간을 저장하기 위한 변수
        
                for(int i = 1; i < N+1; i++) {
                    result[i] = timeToConstruct.get(i-1);
                    if(in[i] == 0) {
                        q.add(i);
                    }
                }
                while(!q.isEmpty()) {
                    //1.큐에서 꺼내옴
                    int now = q.poll();
                    //2.연결된 곳을 순회
                    for(int next: adjList[now]) {
                        result[next] = Math.max(result[next], result[now] + timeToConstruct.get(next-1));
                        in[next]--;
                        //3.갈 수 있는가
                        if(in[next] == 0) {
                            //4.큐에 넣음
                            q.add(next);
                        }
                    }
                }
                System.out.println(result[W]);
            }
        }

   2. Python 3

      • from collections import deque
        import sys
        input=sys.stdin.readline
        
        T = int(input())
        
        for _ in range(T):
            N,K = map(int, input().split())
            timeToConstruct = list(map(int, input().split()))
        
            adjList = [[] for _ in range(N+1)]  # 인접행렬
            inDegree = [0 for _ in range(N+1)]  # 차수
        
            for _ in range(K):
                start,end = map(int,input().split())
                adjList[start].append(end)
                # 단방향이므로
                inDegree[end]+=1
        
            W = int(input())
        
            # BFS
            q = deque();
            result = [0 for _ in range(N+1)]
        
            for i in range(1,N+1):
                result[i] = timeToConstruct[i-1]
                if inDegree[i]==0:
                    q.append(i)
        
            while q:
                now = q.popleft()
                for nex in adjList[now]:
                    result[nex] = result[nex] if result[nex] > result[now] + timeToConstruct[nex-1] else result[now] + timeToConstruct[nex-1];
                    inDegree[nex]-=1
        
                    if inDegree[nex] == 0:
                        q.append(nex);
        
            print(result[W])

• 결과 - 1달전에 풀었던 문제이기도 하다.