N-Queen

이현빈·2021년 7월 28일
0

문제

프로그래머스 N-Queen

문제풀이

너무나도 유명한 대표적인 backtracking 문제 N-Queen 문제이다.

처음엔 체스판인 이차원 배열 board를 만들어 갈 수 있는 곳을 marking하면서 해결하려했으나 n이 커질수록 board를 생성하는데 걸리는 시간이 커져 효율성에서 실패하였다.

그래서 좀 더 효율적으로 코드를 작성하기 위해 고민해보았다. 그 결과 일차원 배열만으로도 같은 열에 있는 말을 체크할 수 있고, 수학적으로 대각선상에 말이 위치할 수 있는 방법이 있다는 것을 알게 되었다. 방법은 다음과 같다.

  1. 같은 열에 위치하는지 체크 -> 일차원 배열안에 값이 같은 원소가 이미 존재하면 같은 열에 이미 체스말이 존재하는 것이다.
  2. 현재 체스말의 위치가 (rowcur,colcur)(row_{cur}, col_{cur})이고 비교하고자 하는 말의 위치를 (rowpre,colpre)(row_{pre}, col_{pre})라고 하면, rowcurrowpre=colcurcolpre|row_{cur} - row_{pre}| = |col_{cur} - col_{pre}|이면 두 말은 대각선상에 위치하는 것이다.

마지막으로 같은 행에 대한 체크는 재귀적으로 다음 깊이로 넘어갈 때 행을 +1씩 증가시켜 같은 행에 위치하지 않는다는 것이 보장되므로 굳이 따로 체크하지 않아도 된다.

def solution(n):
    global answer
    answer = 0

    def search(k, board):
        global answer
        if k == n:
            answer += 1
        else:
            for i in range(n):
                tmp_board = board[::]
                
                for r, c in tmp_board:
                    if i == c or abs(k-r) == abs(i-c):
                        break
                else:
                    tmp_board.append((k, i))
                    search(k+1, tmp_board)

                
    search(0, [])
    return answer

다른 사람의 풀이를 보니 행, 열, 대각선 각각을 체크할 수 있는 일차원 배열 3개를 만들어 더 효율적으로 푸는 방법도 있던 것 같은데 참고해봐야겠다.

profile
익숙해질때까지 한걸음씩

0개의 댓글