1767. 프로세서 연결하기

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

아놔................

resultCpuNum = canCpuNum;

이 한줄을 추가하지 않아, 디버깅 시간 엄청 잡아먹었네요.

다행인건, 생각한 알고리즘의 문제는 아니었네요.

50개의 테스트 케이스 중에서 49개만 맞다고 나오길래,

예외 테스트 케이스만 생각하다보니,.....

왜케 실수를 하지;;;;;;;;;;;

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 1시간 13분) import java.util.Scanner; public class Q1767 { static int mapSize, cpuNum; static int[][] map; static int[][] cpuPositions = new int[12][2]; static int resultCpuNum; static long resultLength; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { resultCpuNum = -1; resultLength = 0; mapSize = sc.nextInt(); map = new int[mapSize][mapSize]; cpuNum = 0; for (int j = 0; j < mapSize; j++) { for (int k = 0; k < mapSize; k++) { int value = sc.nextInt(); if (value != 0) { map[j][k] = 1; cpuPositions[cpuNum][0] = j; cpuPositions[cpuNum][1] = k; cpuNum += 1; } } } solution(0, 0, 0); System.out.println("#" +i + " "+ resultLength); } } static void solution(int nowCpuNum, int canCpuNum, long tempLength) { if (nowCpuNum == cpuNum) { if (resultCpuNum == -1) { resultCpuNum = canCpuNum; resultLength = tempLength; } else if (resultCpuNum < canCpuNum) { resultCpuNum = canCpuNum; resultLength = tempLength; } else if (resultCpuNum == canCpuNum && resultLength > tempLength) { resultLength = tempLength; } return; } int nowY = cpuPositions[nowCpuNum][0]; int nowX = cpuPositions[nowCpuNum][1]; if (nowY == 0 || nowY == mapSize-1 || nowX == 0 || nowX == mapSize-1) { //테두리에 붙어있으면 solution(nowCpuNum+1, canCpuNum+1, tempLength); } else { //상 boolean isPossible = true; for (int i = nowY-1; i >=0; i--) { if (map[i][nowX] != 0) { isPossible = false; break; } } if (isPossible) { for (int i = nowY-1; i >=0; i--) { map[i][nowX] = 1; } solution(nowCpuNum+1, canCpuNum+1, tempLength+nowY); for (int i = nowY-1; i >=0; i--) { map[i][nowX] = 0; } } //하 isPossible = true; for (int i = nowY+1; i < mapSize; i++) { if (map[i][nowX] != 0) { isPossible = false; break; } } if (isPossible) { for (int i = nowY+1; i < mapSize; i++) { map[i][nowX] = 1; } solution(nowCpuNum+1, canCpuNum+1, tempLength+(mapSize-1-nowY)); for (int i = nowY+1; i < mapSize; i++) { map[i][nowX] = 0; } } //좌 isPossible = true; for (int i = nowX-1; i >=0; i--) { if (map[nowY][i] != 0) { isPossible = false; break; } } if (isPossible) { for (int i = nowX-1; i >=0; i--) { map[nowY][i] = 1; } solution(nowCpuNum+1, canCpuNum+1, tempLength+nowX); for (int i = nowX-1; i >=0; i--) { map[nowY][i] = 0; } } //우 isPossible = true; for (int i = nowX+1; i < mapSize; i++) { if (map[nowY][i] != 0) { isPossible = false; break; } } if (isPossible) { for (int i = nowX+1; i < mapSize; i++) { map[nowY][i] = 1; } solution(nowCpuNum+1, canCpuNum+1, tempLength+(mapSize-1-nowX)); for (int i = nowX+1; i < mapSize; i++) { map[nowY][i] = 0; } } //걍 실행 solution(nowCpuNum+1, canCpuNum, tempLength); } } }