1767. [SW Test 샘플문제] 프로세서 연결하기 ---- 틀린 답 ---- 어디가 틀렸지?

Solution.java

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

public class Solution {
	
	public static boolean isAvailableWest(int[][] mat, int nrow, int ncol) {
		for (int i = 0; i < ncol; ++i) {
			if (mat[nrow][i] == 1 || mat[nrow][i] == 2) {
				return false;
			}
		}
		return true;
	}
	public static boolean isAvailableEast(int[][] mat, int nrow, int ncol) {
		for (int i = ncol + 1; i < mat.length; ++i) {
			if (mat[nrow][i] == 1 || mat[nrow][i] == 2) {
				return false;
			}
		}
		return true;
	}
	public static boolean isAvailableNorth(int[][] mat, int nrow, int ncol) {
		for (int i = 0; i < nrow; ++i) {
			if (mat[i][ncol] == 1 || mat[i][ncol] == 2) {
				return false;
			}
		}
		return true;
	}
	public static boolean isAvailableSouth(int[][] mat, int nrow, int ncol) {
		for (int i = nrow + 1; i < mat.length; ++i) {
			if (mat[i][ncol] == 1 || mat[i][ncol] == 2) {
				return false;
			}
		}
		return true;
	}
	
	public static boolean isCore(int[][] mat, int nrow, int ncol) {
		if (mat[nrow][ncol] == 1) {
			return true;
		}
		return false;
	}
	public static boolean isEdge(int[][] mat, int nrow, int ncol) {
		if (nrow == 0 || ncol == 0 || 
			nrow == mat.length - 1 || ncol == mat.length - 1) {
			return true;
		}
		return false;
	}
	public static boolean isOutBound(int[][] mat, int nrow, int ncol) {
		if (nrow < 0 || ncol < 0 || 
			nrow >= mat.length || ncol >= mat.length) {
			return true;
		}
		return false;
	}
	public static boolean isLastPlus1(int[][] mat, int index) {
		if (index == (mat.length * mat.length)) {
			return true;
		}
		return false;
	}
	
	public static void demolishRoadNorth(int[][] mat, int nrow, int ncol) {
		for (int i = 0; i < nrow; ++i) {
			mat[i][ncol] = 0;
		}
	}
	public static void demolishRoadSouth(int[][] mat, int nrow, int ncol) {
		for (int i = nrow + 1; i < mat.length; ++i) {
			mat[i][ncol] = 0;
		}
	}
	public static void demolishRoadWest(int[][] mat, int nrow, int ncol) {
		for (int i = 0; i < ncol; ++i) {
			mat[nrow][i] = 0;
		}
	}
	public static void demolishRoadEast(int[][] mat, int nrow, int ncol) {
		for (int i = ncol + 1; i < mat.length; ++i) {
			mat[nrow][i] = 0;
		}
	}
	
	public static int constructRoadNorth(int[][] mat, int nrow, int ncol) {
		int length = 0;
		for (int i = 0; i < nrow; ++i) {
			mat[i][ncol] = 2;
			++length;
		}
		return length;
	}
	public static int constructRoadSouth(int[][] mat, int nrow, int ncol) {
		int length = 0;
		for (int i = nrow + 1; i < mat.length; ++i) {
			mat[i][ncol] = 2;
			++length;
		}
		return length;
	}
	public static int constructRoadWest(int[][] mat, int nrow, int ncol) {
		int length = 0;
		for (int i = 0; i < ncol; ++i) {
			mat[nrow][i] = 2;
			++length;
		}
		return length;
	}
	public static int constructRoadEast(int[][] mat, int nrow, int ncol) {
		int length = 0;
		for (int i = ncol + 1; i < mat.length; ++i) {
			mat[nrow][i] = 2;
			++length;
		}
		return length;
	}
	
	public static int max = 0; // nConnected
	public static int min = Integer.MAX_VALUE; // lengthOfRoad
	
	public static void go(int[][] mat, int index, int nConnected, int lengthOfRoads) {
		int y = index / mat.length; // nrow
		int x = index % mat.length; // ncol
		
		//System.out.println(index + " " + y + " " + x); // debug
		
		if (!isLastPlus1(mat, index) && isOutBound(mat, y, x)) {
			return;
		}
		
		if (isLastPlus1(mat, index)) {
			if (nConnected > max) {
				max = nConnected;
				min = lengthOfRoads;
				//printMat(mat); // debug
			} else if (nConnected == max) {
				min = Math.min(min, lengthOfRoads);
				//printMat(mat); // debug
			}
			return;
		}
		
		if (isCore(mat, y, x)) {
			if (isEdge(mat, y, x)) {
				go(mat, index + 1, nConnected + 1, lengthOfRoads);
			} else {
				if (isAvailableNorth(mat, y, x)) {
					int nbuilt = constructRoadNorth(mat, y, x);
					go(mat, index + 1, nConnected + 1, lengthOfRoads + nbuilt);
					demolishRoadNorth(mat, y, x); // backtrack
				}
				if (isAvailableEast(mat, y, x)) {
					int nbuilt = constructRoadEast(mat, y, x);
					go(mat, index + 1, nConnected + 1, lengthOfRoads + nbuilt);
					demolishRoadEast(mat, y, x);
				}
				if (isAvailableSouth(mat, y, x)) {
					int nbuilt = constructRoadSouth(mat, y, x);
					go(mat, index + 1, nConnected + 1, lengthOfRoads + nbuilt);
					demolishRoadSouth(mat, y, x);
				}
				if (isAvailableWest(mat,  y, x)) {
					int nbuilt = constructRoadWest(mat, y, x);
					go(mat, index + 1, nConnected + 1, lengthOfRoads + nbuilt);
					demolishRoadWest(mat, y, x);
				}
				go(mat, index + 1, nConnected + 0, lengthOfRoads); // no constructions
			}
		} else {
			go(mat, index + 1, nConnected + 0, lengthOfRoads); // no constructions
		}
		
	}
	
	@Deprecated
	public static void print2(int[][] mat2, boolean[][] mat) {
		for (int i = 0; i < mat.length; ++i) {
			for (int j = 0; j < mat.length; ++j) {
				if (mat[i][j]) {
					System.out.print(2 + " ");
				} else if (mat2[i][j] == 1) {
					System.out.print(mat2[i][j] + " ");
				} else {
					System.out.print(0 + " ");
				}
			}
			System.out.println();
		}
		System.out.println();
	}
	
	@Deprecated
	public static void printMat(boolean[][] mat) {
		for (int i = 0; i < mat.length; ++i) {
			for (int j = 0; j < mat.length; ++j) {
				if (mat[i][j]) {
					System.out.print(2 + " ");
				} else {
					System.out.print(0 + " ");
				}
			}
			System.out.println();
		}
		System.out.println();
	}
	
	@Deprecated
	public static void printMat(int[][] mat) {
		for (int i = 0; i < mat.length; ++i) {
			for (int j = 0; j < mat.length; ++j) {
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void main(String args[]) throws NumberFormatException, IOException {
		final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int nTestcases = Integer.parseInt(br.readLine().trim());
		final StringBuilder ret = new StringBuilder();
		
		for (int testcase = 1; testcase <= nTestcases; ++testcase) {
			// input
			final int sizeMat = Integer.parseInt(br.readLine().trim()); // !
			final int[][] mat = new int[sizeMat][sizeMat]; // !
			for (int nrow = 0; nrow < sizeMat; ++nrow) {
				final StringTokenizer row = new StringTokenizer(br.readLine());
				for (int ncol = 0; ncol < sizeMat; ++ncol) {
					mat[nrow][ncol] = Integer.parseInt(row.nextToken());
				}
			} // for mat
			//printMat(mat); // debug
			
			// solve
			min = 0;
			go(mat, 0, 0, 0);
			//System.out.println(max); // debug
			int answer = min;
			
			ret.append('#');
			ret.append(testcase);
			ret.append(' ');
			ret.append(answer);
			ret.append('\n');
		} // for testcase
		
		System.out.println(ret);
	} // main()
	
} // public class