[Baekjoon] ACM Craft

ACM Craft

출처: Baekjoon
ACM Craft

문제의 이해

• 처음 문제를 보고 “이 문제는 어떤 알고리즘이나 방법으로 풀어야 하겠다” 라고 생각되어서 문제 페이지 아래 알고리즘 분류를 봤다.
• 다이나믹 프로그래밍, 그래프 이론, 위상정렬 이렇게 3가지가 써있었다.
• 다만 일단은 무식하지만 BF로 풀어보기로 했다. 아마도 시간초과가 날 것이라고 예상했고, 예상대로 였다.
• DP는 문제 내에서 구현하면 되겠지 생각하고 그래프 이론과 위상정렬을 검색해서 이해를 해봤다.
• 처음에는 이해가 잘 가지는 않았지만 보다보니 위상정렬을 사용하면 BF로 푼 것에 비해서 비약적으로 속도를 상승시킬 수 있을 것 같았다.

내가 생각한 풀이 방법

• 엄청나게 어려운 문제는 아니고 알고리즘 공부를 하면서 적용시켜 나가면 충분히 풀 수 있는 문제라고 생각했다.
• 물론 결과적으로 거의 3일을 고민하고, 이것저것 방법을 고민하고, 바꿔가면서 겨우겨우 풀었다.
• 다른 무엇보다 언제나 이런 알고리즘 코딩의 결론은, 막히면 생각하고 생각하고 생각하다가 더 생각이 안나면 방법을 바꿔서 초기화하고 다시 푸는 것이 나을 수도 있다는 것이다.

풀이

첫 번째 풀이 : 시간초과. 실패

• 일단 첫번째 BF로 풀어본 풀이 방법이다.
• BF이기도 하면서 DFS 방식이기도 하다.

package com.algorithm;

import java.util.ArrayList;
import java.util.Scanner;

class Building{
	int buildTime = 0;
	ArrayList<Building> requireBuiling = null;
	public Building(int pTime){
		buildTime = pTime;	//건설시간
		requireBuiling = new ArrayList<>(); //현재 건물을 짓기 위해 필요한 건물LIST
	}
	public void addBuilding(Building pBuilding) {	//조건 건물 추가
		requireBuiling.add(pBuilding);
	}
	public int recursiveBuilding(){
		if(requireBuiling.size() == 0) {	//재귀 탈출 조건(건물을 짓기위한 조건이 없는 건물을 만났을 때)
			return buildTime;
		}

		int max = 0;	//현재 건물을 짓기 위한 조건 건물들 중에서 제일 건설시간이 긴 것을 알아낼 변수
		int returnValue = 0;
		for (Building building : requireBuiling) {
			returnValue = building.recursiveBuilding();	//재귀 탈출 조건을 만날때까지 재귀
			max = max < returnValue ? returnValue : max;	//다른 값이 더 크다면 max값 변경
		}
		return buildTime + max;	//건설 시간값 누적
	}
}


public class Num_1005_origin {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		ArrayList<Building>[] testCase = null;	//테스트케이스 LIST배열

		int testCaseNumber = sc.nextInt();	//테스트 케이스 갯수 입력

		int buildingNumber = 0;
		int ruleNumber = 0;
		int[] target = null;


		testCase = new ArrayList[testCaseNumber];
		target = new int[testCaseNumber];

		//입력된 테스트 케이스 횟수만큼 반복.
		for (int i = 0; i < testCaseNumber; i++) {
			testCase[i] = new ArrayList<>();	
			buildingNumber = sc.nextInt();	//건물의 개수
			ruleNumber = sc.nextInt();		//제한 조건의 개수

			//건물의 건설시간 입력
			for (int j = 0; j < buildingNumber; j++) {
				testCase[i].add(new Building(sc.nextInt()));
			}

			//제한 조건의 수만큼 입력
			for (int j = 0; j < ruleNumber; j++) {
				int requireBuildingNumber = sc.nextInt();	
				int ownNumber = sc.nextInt();

				//				requireBuildingNumber이 ownNumber건물을 짓기위한 필요 조건이다.


				//testCase[i].get(sc.nextInt() - 1).addBuilding(testCase[i].get(sc.nextInt() - 1));

				//배열은 0부터 시작하므로 -1
				//조건이 2 4 라면 ownNumber가 4이고 requireBuildingNumber가 2이다.
				//
				testCase[i].get(ownNumber - 1).addBuilding(testCase[i].get(requireBuildingNumber - 1));
			}

			//지어야하는 특정 건물 W
			target[i] = sc.nextInt();
		}

		//테스트 케이스만큼 출력
		for (int i = 0; i < testCaseNumber; i++) {
			System.out.println(testCase[i].get(target[i] - 1).recursiveBuilding());
		}
	}
}

클래스를 자주 사용해보려고 일부러 빌딩이라는 클래스를 만들어서 풀었다.

두 번째 풀이 : 틀렸습니다. 실패

• 알고리즘 분류에 나와있던 위상정렬을 사용 해보았다. 58%에서 계속해서 실패해서 뭐가 문제인지 확인하려고 다른 사람들 질문을 확인했다.
• 다른 사람들은 위상정렬로 풀었다고 하는데, 난 결국 고민고민하다가 시작지점이 여러개거나 하나에서 출발해서 여러개로 나눠지는 것을 체크하지 못해서 실패했다.
• 어떤 문제에서 어떻게 풀면 되겠다고 떠오르면 그 방식대로 풀면 되는데 그게 안떠오를 때가 있다(많다…)
• 기본 예제는 모두 통과 했는데 질문에 나오는 반례들을 결국 통과하지 못했다.

//1						
//6 6
//10 5 1 1 9 8
//1 2
//1 4
//2 3
//4 5
//3 6
//5 6
//6
//정답 28
//내 코드 32


//1
//10 5
//1 2 3 4 5 6 7 8 9 10
//1 6
//2 7
//3 8
//4 9
//5 10
//6
//정답 7
//내 코드 11

• 아래쪽 반례는 조건을 주면 풀 수 있을 것 같은데 위 반례는 아무리 생각해도 방법이 떠오르지 않았다.
• 그래서 이 풀이는 남겨두고 처음에 풀었던 DFS에 DP를 사용해서 풀어보자고 생각했다.

package com.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;

public class Num_1005_Topological_Sort {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		//테스트케이스 수 
		//건물의 수, 조건의 수
		//건물의 건설 시간(건물의 수 만큼)
		//건물의 조건(조건의 수 만큼)

		int testCase = sc.nextInt();	//테스트 케이스

		int bCount = 0;
		int bRequireCount = 0;
		HashMap<Integer, Integer> bTime = new HashMap<>();
		HashMap<Integer, ArrayList<Integer>> bAdjust = new HashMap<>();
		ArrayList<Integer> queue = new ArrayList<>();
		//		HashMap<Integer, Integer> bDegree = new HashMap<>();
		int[] bDegree = null;
		int target = 0;

		int[] sum = new int[testCase];
		
    //테스트케이스 수 만큼 반복 실행
		for (int p = 0; p < testCase; p++) {
			bTime.clear();
			bAdjust.clear();
			queue.clear();
      //모든 저장소 클리어

			bCount = sc.nextInt();  //건물의 수 입력
			bRequireCount = sc.nextInt(); //건물의 조건 갯수 입력
			bDegree = new int[bCount + 1];  //건물의 차수를 저장할 배열(배열이고 0번째를 사용하지 않으려고 +1 해줌)

			//건설 시간 입력
			for (int i = 1; i <= bCount; i++) {
		    int inputTime = sc.nextInt();
				bTime.put(i, inputTime);
				bDegree[i] = 0;
				bAdjust.put(i, new ArrayList<Integer>());
			}

			//배열로 했으니 0부터 시작
			//모든 번호는 -1씩 ㅎ
			for (int i = 1; i <= bRequireCount; i++)
			{
				Integer lBuild = sc.nextInt();
				Integer rBuild = sc.nextInt();

				bAdjust.get(lBuild).add(rBuild);

				bDegree[rBuild]++;
			}
			target = sc.nextInt();

			while(true) {
				for (int i = 1; i <= bCount; i++) {
					if (bDegree[i] == 0) {
						queue.add(i);	//여기 저장되는 i는 차수가 0인 정점
					}
				}

				if(queue.size() == 0) {
					break;
				}

				int max = - 1;
				int bNumber = 0;
				for (int i : queue) {	//차수가 0이 된 모든 정점을 돌면서 연결된 선을 없애면 된다.

					//queue에 있는 값이 target(4)이라면.
					//이 부분이 왜 필요하냐면 차수가 같고, 건설 시간이 같을때 같은 차수에서의 순서가
					//1,4 일때 아래에서 비교하면 1이 순서상 먼저이기 때문에 따로 처리를 해줘야 한다.

					if(i == target) {
						bNumber = i;
						bDegree[i] = -1;
						for (int j = 0; j < bCount + 1; j++) {
							bDegree[j] = -1;
						}
						break;
					}

					if (max < bTime.get(i)) {
						max = bTime.get(i);
						bNumber = i;
					}
					int arraySize = bAdjust.get(i).size();

					for (int j = 0; j < arraySize; j++) {
						int deleteLine = bAdjust.get(i).get(j);
						bDegree[deleteLine]--;
					}
					bDegree[i] = -1;
				}
				sum[p] += bTime.get(bNumber);
				queue.clear();
			}
		}
		for (int i = 0; i < testCase; i++) {
			System.out.println(sum[i]);
		}

	}
}

세 번째 풀이 : 성공

• 첫번째 코드에서 주석을 달아놓은 2군데만 추가 시켰다.
• 알고리즘 문제라서 딱히 상속같은 거 안쓰는데 eclipse에서 같은 패키지에 같은 이름이 있어서 그런지 중복이름이 안되어서 그냥 상속시켰다.
• 첫번째 코드와 달라진 부분이 채 5줄이 안되는데 이렇게 성능이 차이가 난다니.. 진짜 알고리즘은 알다가도 모르겠다.
• 특히 DP는 썼던 것인데도 어떻게 적용해야하지라는 고민이 머리속에서 잠시 있었어서 좀 더 몸에 체득을 시켜야겠다고 생각이 들었다.

package com.algorithm;

import java.util.ArrayList;
import java.util.Scanner;

class Building_valueSave extends Building{
	
	int keepValue = -1;	//DFS 를 했을 때 이미 검사한 부분은 다시 검사하지 않도록 값을 저장해두는 부분
	
	public Building_valueSave(int pTime) {
		super(pTime);
	}

	
	public int recursiveBuilding(){
		if(keepValue != -1) {	// -1이라면 아직 이 루트를 search하지 않은 것이고 값이 있다면 서치 했으므로 
			return keepValue;
		}
		if(requireBuiling.size() == 0) {	
			return buildTime;
		}

		int max = 0;	
		int returnValue = 0;
		for (Building building : requireBuiling) {
			returnValue = building.recursiveBuilding();	
			max = max < returnValue ? returnValue : max;
		}
		
		keepValue = buildTime + max;
		return buildTime + max;
	}
}



public class Num_1005_DP {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		ArrayList<Building_valueSave>[] testCase = null;	

		int testCaseNumber = sc.nextInt();

		int buildingNumber = 0;
		int ruleNumber = 0;
		int[] target = null;

		testCase = new ArrayList[testCaseNumber];
		target = new int[testCaseNumber];

		for (int i = 0; i < testCaseNumber; i++) {
			testCase[i] = new ArrayList<>();	
			buildingNumber = sc.nextInt();
			ruleNumber = sc.nextInt();		

			for (int j = 0; j < buildingNumber; j++) {
				testCase[i].add(new Building_valueSave(sc.nextInt()));
			}

			for (int j = 0; j < ruleNumber; j++) {
				int requireBuildingNumber = sc.nextInt();	
				int ownNumber = sc.nextInt();
				testCase[i].get(ownNumber - 1).addBuilding(testCase[i].get(requireBuildingNumber - 1));
			}

			target[i] = sc.nextInt();
		}

		for (int i = 0; i < testCaseNumber; i++) {
			System.out.println(testCase[i].get(target[i] - 1).recursiveBuilding());
		}
	}
}

마무리

• 진짜 첫 번째 풀이 코드는 금방 짰는데 두 번째 풀이에서 거의 2일 잡아먹은 느낌이다. 처음에는 RunTime Error가 미친듯이 떠서 그거 수정한다고 같은 코드를 다른 방식으로 짰고
• 그 다음에는 58%에서 계속해서 틀려서 정말 너무 고생했다.
• 솔직히 두 번째 풀이에서 포기하고 싶은 마음이 진짜 컸는데 코드 껐다가 다시 킨게 몇번이다.
• 다음에 좀 더 빨리 해보자.