99클럽 코테 스터디 16일차 TIL [완전탐색 - dfs]

 

- 오늘의 학습 키워드 : 완전탐색 - dfs

[문제 이름 :   (소수 찾기, Lv2) ]

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

내가 작성한 코드는 아래와 같다.

class Solution {
    static int answer = 0;
    public int solution(int n) {
        boolean[][] board = new boolean[n][n];
        dfs(board, 0, n);
        return answer;
    }
    
    static void dfs(boolean[][] board, int row, int n) {
        // 모든 퀸이 자리를 잡은 경우
        if (row == n) {
            answer++;
            return;
        }
        
        for(int col=0; col<n; col++) {
            if (canPlace(board, row, col, n)) {
                board[row][col] = true;
                dfs(board, row+1, n);
                board[row][col] = false;
            }
        }
    }
    
    static boolean canPlace(boolean[][] board, int row, int col, int n) {
        for(int i=0; i<row; i++) {
            // 같은 열에 퀸이 있는 경우
            if(board[i][col]) {
                return false;
            }
        }
        
        // 항상 위 -> 아래에서 배치를 시작하므로, 위쪽 대각선만 확인하면 됨
        // 좌상향 대각선에 다른 퀸이 있는지 확인
        for(int i=1; i<=row; i++) {
            if(col - i >= 0 && board[row-i][col-i]) {
                return false;
            }
        }
        
        // 우상향 대각선에 다른 퀸이 있는지 확인
        for(int i=1; i<=row; i++) {
            if(col + i < n && board[row-i][col+i]) {
                return false;
            }
        }
        return true;
    }
}

[풀이 과정]

1. dfs로 각 체스판 배열에서 퀸이 된다고 가정해보며 순회를 돌린다.

2. canPlace()에서 퀸이 위치할 수 있는지를 판단한다. (0,0)에서 부터 dfs가 (n-1,n-1)까지 탐색하므로, 아래 대각선은 확인할 필요 없이 왼쪽 위 대각선, 오른쪽 위 대각선에서만 퀸이 위치하는지 확인해주면 된다.

3. canPlace()가 true이면, 퀸을 위치할 수 있는 것이므로, board에 퀸을 위치시키고, 해당 위치에서 다시 dfs()를 재귀로 돌려 다음 퀸이 올 수 있는지를 판단한다.

4. 총 퀸이 만족하도록 배치할 수 있는 방법의 수(answer)만 리턴한다.

 

재귀 문제는 늘 익숙하면서도 익숙하지 않은(?) 느낌이다.

dfs()에 대한 개념만 충분하다면 어렵지 않게 풀 수 있는 문제였다.

풀이 시간 : 30분

 

내일은 DFS 백준 문제들을 풀어보려고 한다.

프로그래머스