반응형

https://www.acmicpc.net/problem/9663

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

퀸의 특성을 이해하면 쉽게 풀 수 있는 문제입니다.

 

 

퀸은 가로 세로 대각선 방향의 모든 기물을 잡을 수 있습니다. 따라서 한 줄에는 하나의 퀸만 있을 수 있다는 점을 활용하여서 퀸을 놓을 때마다 좌표를 배열에 저장해줍니다.

 

재귀 호출을 할 때 퀸을 놓을 때마다 y값을 1씩 증가시킬 예정이므로 y값은 따로 저장하지 않습니다.

 

qx [15], up [30], down [30] 배열을 만들어 qx 배열에는 퀸의 x좌표를 up 배열에는 오른쪽 위 대각선 방향의 좌표, down 배열에는 오른쪽 아래 대각선 방향의 좌표를 각각 저장해줍니다.

 

또한 대각선 방향의 좌표들의 특성은 아래와 같기 때문에 up [y+x], down [y-x+N-1]을 각각 저장해 주어 퀸의 대각선 방향에 다른 퀸이 있는지 체크할 수 있습니다.

 

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
 
using namespace std;
 
int N;
int qx[15];        //퀸의 x좌표 저장
int up[30];        //퀸의 오른쪽 위 대각선 방향 체크
int down[30];    //퀸의 오른쪽 아래 대각선 방향 체크
int cnt;
int ans;
 
int check(int y, int x)    //y,x 좌표에 퀸을 놓을 수 있는지 체크하는 함수
{
    if (qx[x] || up[y + x] || down[y - x + N - 1]) {
        return 0;        //놓을 수 없다면 0 return
    }
 
    return 1;            //놓을 수 있다면 1 return
}
 
void dfs(int y)            //한 줄에 하나의 퀸만 들어갈 수 있으므로 
{                        //퀸을 놓으면 바로 y+1값으로 dfs 진행
    if (cnt == N) {
        ans++;
        return;
    }
    if (y >= N) {
        return;
    }
 
    for (int x = 0; x < N; x++) {
        if (check(y, x))
        {
            qx[x]++;        //x좌표 저장
            up[y + x]++;    //대각선 방향 저장
            down[y - x + N - 1]++;
            cnt++;
            dfs(y + 1);
            cnt--;
            qx[x]--;
            up[y + x]--;
            down[y - x + N - 1]--;
        }
    }
}
 
int main()
{
    cin >> N;
 
    dfs(0);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
반응형

https://www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제의 핵심은 조합을 뽑을 수 있는가 없는가입니다.

 

주어지는 치킨집들 중에서 맥시멈의 치킨집들을 조합으로 모두 뽑아내서 각 치킨집 중 가장 가까운 치킨집들의 거리를 각각 sum에 더해주고 그중 가장 작은 값을 ans에 경신시켜주어서 답을 내면 되는 아주 간단한 방식입니다.

 

처음에는 bfs를 통해서 가장 가까운 치킨집을 구하려고 했었지만 문제에도 나와있듯이 치킨집까지의 거리는 |r1-r2| + |c1-c2|이므로 조합으로 뽑은 모든 치킨집에 대입시켜 가장 가까운 치킨집을 선택하면 됩니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct pos {            //각 좌표를 저장하기 위한 pos struct
    int y;
    int x;
};
 
int N, M;    
int arr[50][50];        //맵
vector<pos> chicken;    //치킨집의 좌표를 저장할 vector
pos box[13];            //조합을 저장할 배역
int sum;
int ans = 987654321;
 
void dfs(int level, int num)
{
    if (level == M)
    {
        sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    int min = 987654321;
                    for (int k = 0; k < M; k++) {
                        int y = box[k].y;        //조합으로 뽑은 치킨집의 좌표를 추출
                        int x = box[k].x;        //거리를 계산 후 dist에 저장
                        int dist = abs(y - i) + abs(x - j);
                        if (min > dist) {        //가장 작은 dist를 min에 저장
                            min = dist;
                        }
                    }
                    sum += min;            //sum에 min을 더함
                }
            }
        }
        if (ans > sum) {            //가장 작은 sum을 ans에 경신
            ans = sum;
        }
        return;
    }
 
    for (int i = num; i < chicken.size()-M+1+level; i++) {
        box[level] = chicken[i];
        dfs(level + 1, i + 1);
        box[level] = { 0,0 };
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];        
            if (arr[i][j] == 2) {    //치킨집들을 chicken vector에 push
                chicken.push_back({ i,j });
            }
        }
    }
 
    dfs(0, 0);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29

+ Recent posts

티스토리툴바