99클럽 코테 스터디 16일차 TIL / [프로그래머스] N-Queen

오늘의 학습 키워드

---

DFS

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12952

• 플랫폼: 프로그래머스
• 문제명: N-Queen
• 난이도: Lv2

풀이

---

import java.util.*;

class Solution {
    
    static int answer;
    static List<Point> queens = new ArrayList<>();
    
    public int solution(int n) {
        dfs(0, n);
        return answer;
    }
    
    public void dfs(int depth, int n) {
        // 모두 배치한 경우 answer + 1
        if(depth == n) {
            answer++;
            return ;
        }
        
        // 길이가 n인 정사각형에 n개의 퀸을 넣어야 하므로, 한 row에 하나의 퀸은 반드시 들어감
        int row = depth;
        
        for(int col = 0; col<n; col++) {
            if(isPossible(row, col)) {
                queens.add(new Point(row, col));
                dfs(depth + 1, n);
                queens.remove(queens.size() - 1);
            }
        }
    }
    
    private boolean isPossible(int row, int col) {
        // 세로, 대각선에 위치한 퀸이 있는지 확인
        for(Point p : queens) {
            if(p.col == col || Math.abs(p.row - row) == Math.abs(p.col - col)) {
                return false;
            }
        }
        
        return true;
    }
    
    public static class Point {
        int row;
        int col;
        
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

접근

• N*N 크기의 정사각형에 N개의 퀸을 배치하려면 한 row에 하나의 퀸은 반드시 배치되어야 합니다.
• 따라서 DFS를 통한 탐색을 진행할 때, depth는 row로써 활용했고, 어떤 컬럼에 배치할지만 확인했습니다. 한 row에 하나의 퀸만 배치하기에 가로를 제외한 세로, 대각선만 체크합니다.
  • 배치 가능 여부 체크를 위해 배치된 퀸의 좌표값을 queens 리스트에 저장하여 이전에 배치한 퀸의 개수만큼만 순회했습니다.

소요 시간

20분