M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 51 - N-Queens

1 분 소요

문제

leetcode 51 - N-Queens 풀러가기

문제 분석

  • 문제 분석

    이 문제는 Queen을 넣을 수 있는지 계속 판단하면서, 넣을 수 있다면 넣고 다음 줄을 살펴보고 넣을 수 없다면 다시 이전 줄의 상태로 돌아가야 한다.

    ex. [2,2]에 Queen을 넣었다면 3번째 줄을 살펴보고 넣을 수 있는 column이 없다면 다시 2번째 줄로 돌아가서 [2,3]에 넣어본다.

    따라서 조건을 만족하면, 넣는 과정이 반복되므로 재귀를 이용할 수 있다.

    재귀를 통해 다시 함수를 호출 하기 전에, 현재 상태에 대한 표식을 해두고 다음 함수에서 queen을 넣을 수 없다고 판단이 되어 함수가 실행이 끝나고 돌아왔으면 해당 상태에 대한 표식을 없애야 한다.(백 트래킹)

    ex. [2,2]에 Queen을 넣었다면 넣었다는 표식을 해두고, 3번째 줄을 살펴본다. 하지만 넣을 수 있는 column이 없다면 함수가 실행이 끝나고 다시 [2,2]의 함수 상태로 돌아가기 때문에 [2,2]의 표식을 삭제해주고 다음 column으로 이동해야 한다.(이해가 가지 않는다면 코드를 보자.)

  • Queen이 있는지 없는지 확인

    • Queen은 본인이 속한 대각선, 상, 하에 공격을 가할 수 있다.
    • row를 내려가면서 확인하도록 할 것 이므로, column과 대각선에 Queen이 있는지 확인해야 한다.
      • check_column을 통해 현재 column에 Queen이 있는지 파악
      • 좌상향 대각선 : row-column으로 구분할 수 있다.(이해가 안된다면 그림으로 그려보면 이해 될 수 있다.)
      • 우상향 대각선 : row+column으로 구분 할 수 있다.

문제 풀이(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    class Solution {
    public:
        vector<bool> check_column;
        vector<bool> check_rr;
        vector<bool> check_ll;
        
        vector<vector<string>> ans;
        vector<string> tmp;
        
        vector<vector<string>> solveNQueens(int n) {
            
            if(n == 1){
                return ;
            }
            
            check_column.resize(n, false);
            check_rr.resize(n*2, false);
            check_ll.resize(n*2, false);
            
            cal(0, n);
            
            return ans;
        }
        
        void cal(int r, int n){
            
            if(r == n){
                ans.push_back(tmp);
            }
            
            for(int j = 0;j<n;j++){
                if(check(r, j, n)){
                    tmp.push_back(make_str(j,n));
                    check_column[j]=true;
                    check_rr[r+j] = true;
                    check_ll[r-j+n] = true;
                    
                    cal(r+1, n);
                    
                    check_column[j] = false;
                    check_rr[r+j] = false;
                    check_ll[r-j+n] = false;
                    
                
                    tmp.pop_back();      
                }
            }
        }
        
        string make_str(int j, int n){
            string str = "";
            for(int i =0;i<n;i++){
                if(i==j){
                    str+='Q';
                }else{
                    str+='.';
                }
            }
            return str;
        }
        
        bool check(int r, int c, int n){
            
            if(check_column[c]){
                return false;
            }
            if(check_rr[r+c]){
                return false;
            }
            if(check_ll[r-c+n]){
                return false;
            }
            return true;
        }
    };
    		cs
    • 25~48번째 줄 : row를 증가시키면서 함수를 호출한다.
      • 32~43번째 줄 : Queen을 놓을 수 있다고 판정되면, 해당 string을 만들고 Queen을 놓았다는 표식을 한다. 그리고 다음 줄을 탐색하기 위해 row를 증가시켜서 재귀 함수 호출을 한다.
        • 함수가 돌아왔으면, 다시 해당 표식을 없애준다.
        • 좌상향 대각선에 r-c+n을 했는데, 그 이유는 r-c를 할 경우에 음수가 나올 수 있기 때문이다.

    Runtime: 8 ms, faster than 79.67% of C++ online submissions for N-Queens.

    Memory Usage: 7.8 MB, less than 5.88% of C++ online submissions for N-Queens.

    n을 재귀함수 호출 할 때마다 넣었는데, 그냥 n을 전역에서 상수로 두는 게 더 나을 듯 하다.






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고