[알고리즘 스터디] 스터디 시작 및 1주차 활동 기록

스터디 소개

알고리즘 스터디는 한 주동안 1개 이상의 알고리즘 문제를 풀고 일요일마다 모여 각자 풀이한 문제의 접근 및 해결 방법에 대해 공유하는 스터디입니다.
활동 기록은 기록자가 풀이한 문제를 위주로 기술될 예정이며, 스터디 레포지토리에서 더 많은 문제 풀이를 확인해보실 수 있습니다.

GitHub - gdscewha-3rd/Study-Algorithm: GDSC EWHA 알고리즘 스터디 레포지토리입니다.

---

GDCS 알고리즘 스터디 1주차(3/27) 활동 기록입니다.
1주차에는 백트래킹으로 유명한 N-Queen 문제에 대한 풀이를 공유하였습니다.

 

문제 소개

 

문제 접근 방식

• 체스판은 행, 열로 이루어져 있다.
  → 2차원 배열을 써보자.
• 퀸은 가로-세로-대각선 방향을 공격할 수 있다.
  → 다른 퀸과 행 번호와 열 번호의 차이값이 같으면 같은 대각선 상에 위치하므로 안 된다.
  → 행-열에는 하나의 퀸만 존재할 수 있다.
• 배열의 특정 위치에 퀸을 놓아보면서 진행하다가 더 이상 안되면 탐색을 멈추고 되돌아가서 다른 자리로 이동한다.

 

해법을 찾는데 결정적이었던 깨달음

❗ int arr[행] = [열] 로 생각하기

행, 열이라는 개념 때문에 자연스럽게 2차원 배열로 생각했지만 이 문제는 1차원 배열로 충분히 풀이가 가능하다.
어차피 한 행에 퀸은 하나밖에 들어가지 못하기 때문에 몇 번째 행에는 몇 번째 열이 가능하다를 표현하면 된다.
즉, 인덱스는 행이고, 배열 값은 열이다.

 

문제 풀이 로직

1. 같은 행에 1개의 퀸만 가능하다는 전제로 0번 행부터 탐색 시작
2. 총 n개의 루프를 돌면서(n개의 열 탐색) 해당 위치에 퀸을 둬도 되는지 검사 → 함수 이용
3. 함수에서는 현재 행까지 루프를 돌면서 이전에 둔 퀸이 공격 가능한지 검사 → 두 조건(행-열, 대각선) 고려
4. 함수에서 퀸을 둘 수 있는 위치에 해당하는 열을 발견하면 다음 행으로 넘어가고 없다면 이전으로 되돌아감
5. 반복
6. 만약 이번 행이 마지막 행(n번째 행)이라면 n개의 퀸을 놓은 것이므로 count++

 

문제 풀이

#include <stdio.h>
#include <stdlib.h>

int board[15];
int n, count = 0;

int checkCondition(int row) {
    for (int i = 0; i < row; i++) { // 상위 행들에 대해 반복
        // 현재 행의 열 == 상위 행의 열 (같은 열에 있는 경우) 혹은 현재 행 - 상위 행 == 현재 열 - 상위 열(같은 대각선상에 있는 경우) 이면
        if (board[row] == board[i] || row - i == abs(board[row] - board[i])) {
            return 0; // row 행에 col번째 열은 불가능. 다시 돌아간다.
        }
    }
    return 1; // for문을 무사히 통과했다면 이 행은 통과
}

void nQueen(int row) {
    if (row == n) { // 모든 행을 다 통과했다면
        count++; // 횟수 하나 세기
        return;
    }

    for (int col = 0; col < n; col++) {
        board[row] = col; // row 행에 col번째 열을 넣어보고
        if (checkCondition(row)) { // 이 행에서 가능한지 검사
            nQueen(row + 1); // 가능하면 다음 행으로 넘어감
        }
    }
}

int main() {
    scanf("%d", &n);
    nQueen(0);
    printf("%d", count);
    return 0;
}

---

더 좋은 접근 방법이나 풀이법이 있다면 언제든지 댓글 남겨주세요😊