[SWEA] 1767. 프로세서 연결하기

 2015-12-26 오후 2시 30분 부터 5시까지 시도해보았던 문제입니다..... 3시간동안 2문제를 풀어보려고 했으나 이문제도 풀지 못하고 끝나버렸습니다. 밑의 코드는 첫 제출에서 6개의 테스트 케이스만을 맞추고 시간초과에 걸렸습니다. 딱 봐도 코드가 더럽고 한눈에 안들어오네요. 계속 시뮬레이션으로 모든 경우를 직접 만들어보려고 집착했던게 큰 것 같습니다. 벡터도 사용하고 불필요한 과정을 여러 번 거치다 보니 시간초과가 난 것 같습니다.

 

 

 

 구글링으로 코드를 참고하여 제가 직접 짜본 코드입니다. 확실히 코드도 짧고 눈에 잘들어오네요. 복사를 해서 탐색하지 않고 제대로 된 dfs방식으로 탐색하게 됩니다. 직접 map에 전선을 연결하고 끊어보는 과정이 중요하겠네요. 모든 정보를 벡터를 통해 저장하지 않고 단순 함수 호출로 처리한 것도 시간 단축에 큰 요인이라고 생각됩니다.

 

 이 문제에서 중요했던 포인트라고 생각했던 부분은 26번째 라인이라고 합니다. 저 조건문이 없으면 테스트 케이스가 43개 맞고 시간초과가 납니다. 저렇게 현재까지 검사한 개수와 남아있는 코어의 개수의 합이 현재까지 기록되어 있는 최대로 연결가능한 코어 개수보다 작게 되면 탐색하지 않아도 됩니다. 일종의 백트래킹처럼 동작하게 만들어서 시간초과가

나지 않게 됩니다.