hyeoneee's blog

백준 9663번 NQueen 문제.

가장 유명한 백트래킹 문제 nQueen 문제이다.

이전에 시험볼떄 오조오억번 풀어서

달달달~~ 외웠는데

왜 몇년 지나고 다시 풀려고하니 기억이 안나지 ^.ㅜ

휴

두가지 방법으로 풀어 보았다

첫번째는 이전에 공부한 방식

1. 이중 for 문을 쓴 방식

2. for 문을 하나 쓴 방식

1. 이중 for문

열과 행의 정보를 담는 배열을 두개 선언해 주고

해당 열을에 퀸이 있는지,

대각선에 퀸을 놔도 되는지를

체크해준다.

정의를,

열과 행의 정보를 담아준다로

정의해서 이중포문을 썼다.

2. 포문을 하나 쓴 경우

 가지치기 할수 있는 경우를 세개를 정의해서

해당 배열을 3개 선언해주었다.

가. 같은 열에 퀸이 있는지

나. 대각선 체크 y=x 기울기가 1인 대각선 체크

다. 대각선 y=-x 기울기가 2인 대각선 체크

두 개 모두 행을 인자로 두고

재귀를 쓰는것은 똑같다.

휴,, 백트래킹

마스터 함해버자,,,, ^_^,,,,

그럼 이만

뿅!