2019. 06. 07 이머시브 수업 2주차 - 4일(N-Queens)

# N-Queens에 대한 설명

어떤 사이즈의 판이 될지 모르는 n개의 체스판이 있다(4 * 4, 5 * 5, 6 * 6 ...)

n개의 퀸이 서로 겹치지 않는 방향으로 이동해야 한다

퀸은 가로 혹은 세로, 대각선 방향으로 이동이 가능하다

N-Queens를 구현하면서 제일 중요했던부분은

"가로를 기준으로 잡던 세로를 기준으로 잡던 N개에는 1개의 퀸이 있고 이동경로가 겹치지않는다"

이게 핵심이었다

 

N-Queens 구현중

 

# N-Queens 코드분석

 

Helper function :

처음 이 문제를 받아서 열었을때 코드파악만 몇시간이 걸렸다

위 사진에서 보다시피 깔려있는것들이 워낙 많았고 (이 문제에서 중요하다고 했던) Backbone이라는 처음 듣는 라이브러리에..

문제의도파악을 하기위해 우선 this, 매개변수를 뭘로 받는지 찍어보고 하나씩 유추해나가기 시작했다

그래서 내가 파악할 수 있었던건

"체스판에 퀸 또는 룩이 있고 얘네의 이동경로에 걸리는게 있다면 충돌이 일어났으니 불린값으로 그것을 리턴해라 "

이 정도였던것 같다

 

solver function : 

이 문제에 대해서 아직 구현을 하지는 못하였다

그래도 풀어보면서 이해한부분은 아래 사진과 같이 트리형태처럼 구현이 가능할것 같다는점

 

 

"재귀를 돌리는 방법이었다"

가로축과 세로축중 하나를 기준점으로 잡고, 0은 퀸이없다 1은 퀸이있다라는 가정하에 처음 1을 찍어주면 그 줄에는 1이 찍힐수 없다

그럼 다음줄로 넘어가고 그 부분에서 또 배열을 4번 돈다

[[1,0,0,0],

[0,0,0,0],

[0,0,0,0],

[0,0,0,0]]

그럼 그 다음 가능한곳에 찍는다면

[[1,0,0,0],

[0,0,1,0],

[0,0,0,0],

[0,0,0,0]]

이런식으로 그 부분에 1을 찍을 수 있는지없는지를 헬퍼함수를 이용해가면서 재귀를 이용해 풀어갈것이다

4 * 4 의 판 하나에서 계속 순회를 하면서 퀸이 각각 다른자리에서 위치할 수 있는 경우의 수가 몇번인지도

count라는 변수를 통해서 퀸이 4개 찍힐때마다 1씩 증가를 시켜준다면 경우의수도 뽑아낼 수 있을거라 생각했다

---

# N-Queens 결과  

 

결국 시간내에 문제를 해결하지는 못하였다

문제점 1. 문제의도파악을 정확히 캐치하지 못했다는것 (1. 트리구조 2.N-Queens는 한줄에 하나의 퀸이 있어야 한다는것)

문제점 2. 재귀를 돌렸어야 했는데 이중for문을 돌렸다는것

문제점 3. 재귀의 개념은 알고있지만 깊게 들어가면 어떤식으로 돌려야될지 감을 못잡고있다는것이다

 

잘 모른다고 피하지말고 부딪혀보자

부딪혀보고 엎어져봐야 익숙해지고 실력이 쌓인다 !