LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정수 n

2. output: n X n 크기의 체스판에 n개의 퀸을 서로 공격하지 못하는 위치에 놓는 모든 경우 배열로 리턴

   ex) [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

   • 1 <= n <= 9

Idea

퀸이 서로 공격하지 못하는 위치

• 같은 row 위 X
• 같은 col 위 X
• 기울기 1의 대각선 위 X

Solution

1. DFS/구현

   • 각 row 순회
   • 각 col 마다 퀸을 놓을 수 있는지 확인 → 놓을 수 있다면 다음 row로 DFS 탐색

   class Solution {
       var n = 0
       val result = mutableListOf<List<String>>()
       fun solveNQueens(n: Int): MutableList<List<String>> {
           this.n = n
           queen(Array<String>(n){".".repeat(n)}, Array(n){-1}, 0)
           return result
       }
   
       fun queen(board: Array<String>, visited: Array<Int>, height: Int) {
           if (height == n) { // n개의 퀸을 모두 놓았을 경우 결과 추가
               result.add(board.toList())
               return
           }
           for (c in 0 until n) { // 각 col에 대하여 퀸을 놓을 수 있는 지 확인
               if (visited[c] == -1) { // 같은 col에 놓인 퀸이 없다면
                   var canAttack = false
                   for (j in 0 until n) { // 대각선에 위치한 퀸이 있는지 확인
                       if (visited[j] != -1 && Math.abs(c - j) == Math.abs(height - visited[j])) {
                           canAttack = true
                       }
                   }
                   if (!canAttack) { // 대각선에 위치한 퀸이 없는 경우
                       val tmp = ".".repeat(c)+"Q"+".".repeat(n - c - 1)
                       board[height] = tmp
                       visited[c] = height
                       queen(board, visited, height + 1)
                       visited[c] = -1
                       board[height] = ".".repeat(n)
                   }
               }
           }
       }
   }
   

   시간 복잡도: 깊이 탐색(DFS) X 배열 순회(col) X 배열 순회(대각선) = n^3

   

Point

1. 체스판에 퀸 놓는 문제 풀이 방식 → 시간 복잡도는 동일
   • 퀸을 하나씩 놓으면 해당 퀸을 공격 가능한 위치에 퀸이 있는지 확인
   • 퀸을 하나씩 놓으면서 공격 가능한 위치 후보(이후 퀸이 놓을 수 있는)에서 삭제