[C#]백준 9663 N-Queen - Hide

반응형

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

문제 요약

퀸 N개를 서로 공격할 수 없게 놓는 경우의 수 출력하기

 

 

 

참고

https://youtu.be/gcuZ_VGIcn4?si=96vY5Q1qLXZ-O1cl

처음에 이해할 때 도움이 많이 된 영상

 

 

 

풀이(백트래킹)

int n=int.Parse(Console.ReadLine()),r=0,c=0;
//r : 현재까지 퀸을 배치한 행 번호
//c : 퀸을 올바르게 배치한 경우의 수
var q=new int[n]; //q : 각 행마다 퀸을 배치한 열 번호(q[0]=3 -> 0행 3열)

while(true){
    if(r==n) //퀸을 성공적으로 배치했을 때
    {
        c++; //경우의 수+1
        q[--r]++; //이전 행의 다음 열에도 가능한 경우의 수가 있는지 찾기
    }
    else if(q[r]==n) //현재 케이스를 끝까지 다 둘러본 경우(다음 케이스로 넘어갈 준비)
    {
        q[r]=0;
        if(--r<0)break;
        q[r]++; //다음 케이스 시도
    }
    else //검사중
    {
        int d=1;
        for(int i=0;i<r;i++)
            if (q[i]==q[r]||Math.Abs(q[i]-q[r])==r-i){d=0;break;} 
            //퀸이 같은 열 또는 대각선에 있을 때 d=0으로 바꾸고 탐색 중단
            //q[i] == q[r] : 같은 열에 있는지 비교
            //Math.Abs(q[i]-q[r]) == r-i : 대각선에 있는지 비교
            //하나라도 충돌하면 d=0으로 변경하고 for문 탈출
        if(d==1)r++;
        //같은 열이나 대각선에 없으면 r++ 해서 다시 while문 순회
        else q[r]++;
        //d가 1이 아닐 경우 q[r]++(현재 행에서 다음 열로 한칸 이동해서 다른 경우의 수 탐색)
    }

}
Console.Write(c);

※ 여기서 말하는 "케이스" : 첫 번째 퀸을 (0, i)에 놓았을 때의 경우의 수

 

 

 

숏코딩

Console.Write(new[]{0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596}[int.Parse(Console.ReadLine())]);

n이 15까지니까 모든 경우의 수 배열로 만들고 고대로 출력하기

---

머리로는 이해되는데 코딩하는 게 너무 어려움... 그리고 이제 풀어야 되는 문제들이 다 이 정도 수준이겠지 울고 싶다 진짜