[백준 9663번][Java] N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

 

처음에는 퀸을 놓을 때 위치 정보를 스택에 저장했었다. 백트래킹은 보통 재귀호출 이후에 상태정보를 복구해야 되기 때문에 이를 pop 메서드를 이용해 편하게 구현하기 위함이었다.

 

그런데 자꾸 시간초과가 나길래 다른 코드들도 훑어봤지만 코드 패턴은 비슷했다. 도대체 영문을 알 수가 없었는데, Stack의 순회 성능 때문이었다. Stack 역시 List 인터페이스를 구현하고 있기 때문에 그러려니 하고 사용했는데 ArrayList에 비해서 이렇게 차이가 날 줄은 몰랐다. 입력을 14로 주었을 때 Stack으로 했을 떄는 1분이 넘어가도 답을 구하지 못했는데 ArrayList의 경우에는 8초 안에 답을 낼 수 있었다.

 

자료구조의 중요성을 실감했다.

 

...

/*
N-Queen
 */
public class Main {
	static int n;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		List<Location> queenLocations = new ArrayList<>();

		System.out.println(nQueen(0,0,queenLocations));
	}

	private static int nQueen(int row, int queen, List<Location> queenLocations) {
		if(queen == n) return 1;

		int ret = 0;

		for (int i = 0; i < n; i++) {
			if(isValid(row, i, queenLocations)) {
				queenLocations.add(new Location(row, i));

				ret += nQueen(row+1, queen+1, queenLocations);
				queenLocations.remove(queenLocations.size()-1);
			}
		}
		return ret;
	}

	private static boolean isValid(int row, int col, List<Location> queenLocations) {
		for (int i = 0; i < queenLocations.size(); i++) {
			Location location = queenLocations.get(i);
			if(location.row == row || location.col == col
					|| location.row + location.col == row + col
					|| location.row - location.col == row - col) return false;
		}
		return true;
	}
}
class Location {
	int row, col;
	public Location (int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "{row=" + row +
				", col=" + col +
				'}';
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}