[9663] N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

백트래킹 대표 유형 문제다. 예전에 시도했던 문제지만 시간제한에 걸려 풀지 못했던 문제다. 결국 다른 분의 풀이를 확인하고 풀 수 있었다.

 

풀이

해당 문제는 같은 행과 열, 그리고 우측에서 좌측으로 내려오는 대각선과 좌측에서 우측으로 내려오는 대각선이 겹치는지 확인하여 N번의 조건을 백트래킹을 통해 풀어야 한다. 단순하게 매 횟수마다 2차원 배열의 true false를 통해 조건을 탐색하게 된다면 시간 초과가 일어나게 된다.

이번 풀이는 열, 좌측 하행 대각선, 우측 하행 대각선을 담당하는 Bool 타입 1차원 배열을 각각 따로 생성하여 조건을 확인하는 방법이다. 행에 대한 배열이 없는 이유는 한 행에 하나의 퀸만 놓을 수 있기에 따로 퀸을 놓게 되면 바로 다음 행으로 넘어가기 때문이다.

N = 4일 경우의 각 배열의 양상이다. 2차원 보드판 위치의 기준으로 각 배열에 확인해야 하는 인덱스를 넣어 놓았다. 3가지 배열 모두 해당 인덱스에 퀸이 없을 경우에만 퀸을 배치하고 다음 열로 넘어가게 된다.

 

정답 코드