'SW역량테스트' 태그의 글 목록 (3 Page)

SW역량테스트

[BOJ] 14502. 연구소

2019. 8. 4. 17:26

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

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

www.acmicpc.net

n과 m이 최대 8이고 벽은 딱 3개만 세우면 되므로 시간 안에 완전 탐색을 해서 해결할 수 있다.

빈칸에 벽 3개를 세우는 모든 경우를 구해주고 3개를 정할 때마다 BFS로 바이러스를 퍼뜨려서 최대 안전영역의 수를 구해주면 된다. 즉 전형적인 완전 탐색 + BFS 문제이다.

안전 영역의 수는 0인 곳의 수를 미리 cnt 변수에 저장해 두고 바이러스가 퍼질 때마다 cnt에서 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m, ans;
int map[9][9];
bool check[9][9];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
int bfs() {
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
 
    //안전역역의 수
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //안전영역이면 cnt증가
            if (map[i][j] == 0) {
                cnt++;
            } else if (map[i][j] == 2) {
                //바이러스이면 큐에 넣어준다.
                q.push(make_pair(i, j));
                check[i][j] = true;
            }
        }
    }
 
 
    int x, y;
    //바이러스를 퍼뜨린다.
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            //벽
            if (map[nx][ny] == 1) continue;
            //방문 체크
            if (check[nx][ny]) continue;
 
 
            //(nx,ny)로 바이러스 확산
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
 
            //안전영역의 수가 감소한다.
            cnt--;
        }
 
    }
 
    //안전영역의 수를 리턴
    return cnt;
}
 
void solve(int cnt) {
    //벽 3개를 세웠다.
    if (cnt == 3) {
        int tmp = bfs();
 
        //안전영역의 최댓값을 저장
        if (ans < tmp) ans = tmp;
        return;
    }
 
 
    //벽을 세우는 모든 경우를 구해준다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            // (i,j)가 빈칸이면 벽을 세워준다.
            if (map[i][j] == 0) {
                map[i][j] = 1;
                solve(cnt + 1);
                map[i][j] = 0;
            }
 
 
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
 
    solve(0);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14499. 주사위 굴리기 (0)	2019.08.04
[BOJ] 14503. 로봇 청소기 (0)	2019.08.04
[BOJ] 15685. 드래곤 커브 (0)	2019.08.04
[BOJ] 15686. 치킨 배달 (0)	2019.08.04
[BOJ] 16234. 인구 이동 (0)	2019.08.02

[BOJ] 15684. 사다리 조작

2019. 8. 4. 13:37

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

15684번: 사다리 조작

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로

www.acmicpc.net

사실 구현자체는 어렵지 않았는데 시간초과가 계속 나서 한참 고생했던 문제이다...

먼저 문제에서 3개 넘게 사용해야하는 경우에는 -1을 출력하라고 했으므로

가로선을 놓는 모든 경우를 탐색해줄 수 있긴하지만 백트래킹을 잘해줘야한다...ㅠㅠ

내 기준 이 문제에서 중요한 부분!

1. 가로선을 놓을 때 나는 가로선의 시작점을 1로 놓고 끝점을 2(빈 곳은 0)로 놓았다.

단순히 true/false로 놓으면 왼쪽으로 가는지 오른쪽으로 가는지를 다시 알아내야하기 때문이다.

이 아이디어는 사실 다른 곳에서 본거다ㅎㅎ

2. 사다리 타기를 시작할 때, 왼쪽이나 오른쪽으로 열을 이동하는 경우에도 한칸을 내려가도록 해줘야한다.

그렇지 않다면 가로선에서 계속 오른쪽 왼쪽을 왔다갔다하는 무한 루프에 빠질 수 있다.

3. 시간 초과를 해결하기 위한 가장 중요한 부분인데, 가로선을 놓을 곳을 탐색할 때 다시 (1,1)부터 하면 안되고 현재 가로선을 놓아준 행부터 다시 탐색을 시작하도록 현재 행을 매개변수로 넘겨준다.

4. 마지막으로 개인적으로 실수했던 부분인데 1개만 놓는 경우, 2개를 놓는 경우, 3개를 놓는 경우를 각각 해줬었다.

2개를 놓는 경우는 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, h;
int check[32][11];
 
bool ispossible() {
 
    //모든 세로선에 대해서 검사
    for (int i = 1; i <= n; i++) {
        int x = 0;
        int y = i;
 
        //사다리 타기 시작
        while (true) {
            //맨 밑에 도착
            if (x == h + 1) {
                //i번의 결과가 i번이면 break후 에 다음 세로선을 검사
                //그렇지 않은 경우에는 바로 false를 리턴
                if (y == i) break;
                else return false;
            }
 
 
            //1인 경우에는 오른쪽사다리로 이동
            if (check[x + 1][y] == 1) {
                y++;
            }//2인 경우는 왼쪽사다리로 이동
            else if (check[x + 1][y] == 2) {
                y--;
            }
 
            //한칸 내려간다.
            x++;
        }
 
    }
 
 
    return true;
 
}
 
int select(int x, int index) {
 
    //3을 넘어가면 바로 -1을 리턴
    if (index > 3) {
        return -1;
    }
 
    int ans = -1;
 
 
    //x행부터 탐색을 시작
    for (int i = x; i <= h; i++) {
        for (int j = 1; j < n; j++) {
            if (check[i][j] != 0) continue;
            if (check[i][j + 1] != 0) continue;
 
            //i행의 j번과 j+1번에 가로선을 놓는다.
            check[i][j] = 1;
            check[i][j + 1] = 2;
 
 
            //가로선을 놓은 상태에서 사다리 게임의 결과를 바로 확인
            if (ispossible()) {
                //i번 세로선이 i번에 도착한다면 현재 index(사용한 가로선 수)를 ans에 저장
                ans = index;
            }
 
            //현재 가로선을 놓은 상태에서 추가로 다른 곳에 하나 더 놓는 경우를 탐색
            //다음 탐색에서는 i행부터 진행한다.
            int tmp = select(i, index + 1);
 
            //ans가 초기값이라면 다음 탐색에서 받아온 tmp를 저장
            if (ans == -1) ans = tmp;
 
            //다른 곳에 가로선을 놓는 경우를 위해서 다시 가로선을 없애준다.
            check[i][j] = 0;
            check[i][j + 1] = 0;
        }
    }
 
    return ans;
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> h;
    int a, b;
 
    //가로선의 왼쪽점을 1, 오른쪽점을 2로 놓는다.
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        check[a][b] = 1;
        check[a][b + 1] = 2;
    }
 
    //가로선을 추가로 놓지않고 가능하다면 바로 0을 출력
    if (ispossible()) cout << 0 << '\n';
    else {
 
        cout << select(1, 1) << '\n';
    }
 
 
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

[BOJ] 15685. 드래곤 커브

2019. 8. 4. 13:03

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

15685번: 드래곤 커브

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2,

www.acmicpc.net

다들 쉽다고 하는 문제인데 나는 개인적으로 쉽지는 않았다. 실제로 규칙만 금방 알아내면 어렵지는 않다.

하지만 나는 일단 x좌표가 열이고 y좌표가 행이라 처음에 너무 헷갈렸었다....

일반적인 수학에서는 원래 그렇긴하지만 코딩할 때는 보통 r,c이면 r이 행이니까...ㅠ

그리고 처음에 규칙을 좌표에서 찾느라 헤매기도 했다...

이 문제는 세대별로 방향에 규칙이 있다.

문제의 예시를 봐보자.

0세대 드래곤 커브의 방향이 0이었다면, 1세대에 새로 생기는 방향은 1이다.

그리고 다음 2세대에 새로 생기는 방향은 순서대로 2, 1 이다.

그리고 다시 3세대에는 2, 3, 2, 1 방향이 새로 생긴다.

정리해서 보면 다음과 같다.

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1

3세대로 예를 들어보면 다음과 같이 방향이 1씩 증가했음을 알 수 있다.

화살표가 이어진 점은 화살표의 출발점이 이전 세대의 원래 점이고

화살표가 가르키는 점이 90도 회전해서 새로 생기는 점이다.

즉, 이전에 있었던 점의 방향으로부터 1이 더해졌음을 알 수 있다.

1세대와 2세대도 다시 보면 같은 규칙을 가지고 있는 것을 알 수 있다.

위의 규칙을 이용해서 방향 index를 문제에서 주어진 대로 dx와 dy배열에 잘 저장해서 구현해주면 된다.

드래곤 커브를 구했으면 이제 각 칸의 정사각형의 네 꼭짓점이 드래곤 커브에 포함되는지를 구해줘야한다.

드래곤 커브끼리 겹치는 부분이 있을 수도 있으므로 드래곤 커브를 먼저 모두 구한 뒤에 나중에 한번에 계산해준다.

(0,0)부터 시작하여 시작점으로부터 오른쪽, 아래, 오른쪽아래가 드래곤 커브에 포함되어 있는지 검사해주면 된다.

맨 마지막행이나 열에서 범위를 넘어가지 않도록 99번째 행과 99번째 열까지만 검사를 진행한다.

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
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include <vector>
using namespace std;
 
bool check[101][101];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
int x, y, d, g;
vector<int> dir;
 
 
int calc() {
    int cnt = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            //네 꼭짓점을 검사
            if (!check[i][j]) continue;
            if (!check[i + 1][j]) continue;
            if (!check[i][j + 1]) continue;
            if (!check[i + 1][j + 1]) continue;
 
            //모두 포함되어 있다면 cnt 증가
            cnt++;
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
    //0세대 처리
    check[y][x] = true;
    x += dx[d];
    y += dy[d];
    check[y][x] = true;
    dir.push_back(d);
 
 
    int dsize;
    //구해줄 세대 수만큼 진행
    for (int i = 0; i < g; i++) {
        dsize = dir.size();
 
        //회전하여서 이번 세대에서 새로 생길 방향들을 추가해준다.
        for (int j = dsize - 1; j >= 0; j--) {
            dir.push_back((dir[j] + 1) % 4);
        }
 
        dsize = dir.size();
        //새로 생긴 방향들에 대해서만 이동을 진행
        for (int j = (dsize / 2); j < dsize; j++) {
            x += dx[dir[j]];
            y += dy[dir[j]];
            check[y][x] = true;
        }
    }
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    while (n-- > 0) {
        cin >> x >> y >> d >> g;
        
        //새로운 드래곤 커브를 구해 줄 것이므로 방향을 저장해 놓을 벡터를 비워준다. 
        dir.clear();
        solve();
    }
 
 
    //드래곤 커브를 모두 구하고 한 번에 계산해준다
    cout << calc() << '\n';
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14503. 로봇 청소기 (0)	2019.08.04
[BOJ] 14502. 연구소 (0)	2019.08.04
[BOJ] 15686. 치킨 배달 (0)	2019.08.04
[BOJ] 16234. 인구 이동 (0)	2019.08.02
[BOJ] 17281. ⚾ (0)	2019.08.02

[BOJ] 15686. 치킨 배달

2019. 8. 4. 12:36

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

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는

www.acmicpc.net

N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)의 범위를 보고 완전 탐색을 해도 된다는 것을 알 수 있다.

(r1, c1)과 (r2, c2)의 거리는 문제에서 주어졌듯이

|r1-r2| + |c1-c2|

다음과 같은 식을 사용해서 풀 수 있다. BFS로도 풀 수 있지만 위의 식을 이용해서 간단히 풀 수 있다.

먼저 입력을 받을 때, 집과 치킨집의 좌표를 각각 벡터에 넣어준다.

그다음에는 치킨집 중 m개를 고르는 경우를 모두 구해준 후에

각각 m개를 골라줬을 때마다 도시의 치킨 거리를 구해주고 최솟값을 비교하여 저장한다.

치킨 거리는 모든 집에 대해서 구해줘서 각 집의 치킨 거리를 전체 도시 치킨 거리에 더해준다.

각 집의 치킨 거리는 각 집으로부터 폐업하지 않은 모든 치킨집과의 거리를 구해보고

최소 거리가 치킨 거리가 된다.

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
 
int n, m;
int ans;
int map[50][50];
 
vector<pair<int, int>> home;
vector<pair<int, int>> store;
vector<pair<int, int>> selected;
 
int calc() {
    int citylen = 0;
    int homecnt = home.size();
    int hx, hy, sx, sy;
 
 
    //모든 집에대해 치킨거리를 구한다.
    for (int i = 0; i < homecnt; i++) {
        hx = home[i].first;
        hy = home[i].second;
 
        int chickenlen = 10000;
        //모든 치킨집과의 거리를 계산하여 가장 가까운 곳이 치킨거리이다
        for (int j = 0; j < m; j++) {
            sx = selected[j].first;
            sy = selected[j].second;
 
            int tmp = abs(hx - sx) + abs(hy - sy);
            chickenlen = min(chickenlen, tmp);
        }
 
        //도시의 치킨거리에 i번째 집의 치킨거리를 더해준다.
        citylen += chickenlen;
    }
 
    //도시의 치킨 거리를 리턴
    return citylen;
}
 
 
void select(int index, int cnt) {
    //m개를 골랐다
    if (cnt == m) {
        //도시의 치킨거리를 계산한다.
        int tmp = calc();
        ans = min(ans, tmp);
        return;
    }
 
    //모든 가게에 대해 선택을 끝냈다.
    if (index == store.size()) return;
 
    int x = store[index].first;
    int y = store[index].second;
 
    //index번째 가게를 폐업시키지 않는 경우
    selected.push_back(make_pair(x, y));
    select(index + 1, cnt + 1);
 
    //index번째 가게를 폐업시키는 경우
    selected.pop_back();
    select(index + 1, cnt);
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            //집인 경우 home벡터에 추가, 치킨집인 경우 store벡터에 추가
            if (map[i][j] == 1) home.push_back(make_pair(i, j));
            else if (map[i][j] == 2) store.push_back(make_pair(i, j));
        }
    }
 
    //ans에 정답이 될 수 있는 값보다 큰 값을 넣어둔다.
    ans = 10000;
 
    //탐색 시작
    select(0, 0);
 
 
    cout << ans << '\n';
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14502. 연구소 (0)	2019.08.04
[BOJ] 15685. 드래곤 커브 (0)	2019.08.04
[BOJ] 16234. 인구 이동 (0)	2019.08.02
[BOJ] 17281. ⚾ (0)	2019.08.02
[BOJ] 17136. 색종이 붙이기 (0)	2019.08.02

[BOJ] 16234. 인구 이동

2019. 8. 2. 17:09

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

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명

www.acmicpc.net

BFS를 이용해서 인접해 있는 칸(국가)들의 인구를 비교해주고 국경선을 열어줄 수 있다.

이 문제는 일종의 연결 요소 문제인 것 같다. 연결되어 있는 나라들(한 번의 BFS탐색으로 탐색이 가능한 나라들)에 같은 번호를 붙여주고 같은 번호가 붙어있는 나라들끼리 인구이동을 해주면 된다.

인구 이동은 인구이동이 발생하지 않을 때까지 진행한다.

인구이동을 진행하기 위해서는 모든 국가들을 탐색하여 연합국가를 만들어준다.

연합국가에 이미 포함된 국가들은 방문 체크를 통해 다시 탐색하지 않는다.

어렵지 않으므로 자세한 설명은 코드 참고!

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, l, r;
int ans;
int map[50][50];
int check[50][50];
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
 
//bfs로 인접한 국가를 탐색
bool bfs(int x, int y, int num) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = num;
 
    //시작칸의 국가의 인구수도 sum에 더해주고 처음 연함국가 수는 1
    int sum = map[x][y];
    int cnt = 1;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            //방문 체크
            if (check[nx][ny] != 0) continue;
            
            //두 국경사이의 인구 차이를 계산하고 차이가 l보다 작거나 r보다 크면 국경선을 열지 않는다
            int diff = map[x][y] - map[nx][ny];
            if (diff < 0) diff = -diff;
            if (l > diff || diff > r) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = num;
            
            //연합을 할 국가들의 인구수를 모두 더해준다.
            sum += map[nx][ny];
            //연합이 될 국가의 수 증가
            cnt++;
        }
 
    }
 
 
    //cnt값이 초기값보다 증가 했다면 인구 이동이 있었다
    if (cnt > 1) {
 
        //연합을 이루는 국가들의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다
        int newnum = sum / cnt;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j] == num) {
                    map[i][j] = newnum;
                }
            }
        }
 
        return true;
    } //인구 이동이 없었다
    else return false;
 
}
 
 
//모든 국가에 대해서 탐색
bool solve() {
 
    bool flag = false;
    int num = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 0) {
                if (bfs(i, j,num++)) {
                    //한번이라도 인구이동이 있으면 true
                    flag = true;
                }
            }
        }
    }
 
 
    if (flag) return true;
    else return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
 
 
    while (true) {
        //인구 이동을 더 이상 할 수 없으면 break
        if (!solve()) break;
        ans++;
        memset(check, 0, sizeof(check));
    }
 
    cout << ans << '\n';
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 15685. 드래곤 커브 (0)	2019.08.04
[BOJ] 15686. 치킨 배달 (0)	2019.08.04
[BOJ] 17281. ⚾ (0)	2019.08.02
[BOJ] 17136. 색종이 붙이기 (0)	2019.08.02
[BOJ] 17135. 캐슬 디펜스 (0)	2019.08.01

[BOJ] 17281. ⚾

2019. 8. 2. 16:42

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

17281번: ⚾

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에

www.acmicpc.net

예전에 문제를 처음 봤을 때는 시간 안에 제대로 풀지 못했던 문제이다

비트 마스크를 이용해서 풀면 조금 더 쉽게 풀 수 있는 문제였다

먼저,

9명의 선수들의 가능한 모든 타순을 구해보고 경기를 시작하여 점수를 계산한 뒤 가장 높은 득점을 얻는 경우의 득점을 구해주면 된다. 선수를 고를 때, 문제에서 4번 타자는 1번 선수로 고정되어 있으므로 이 부분만 주의해주면 된다.

선수들의 타순을 모두 정해줬다면 경기를 시작해주면 된다.

이닝수만큼 경기를 진행하고 각 이닝은 3아웃이 발생할 때까지 진행한다.

9번선수까지 모두 공격을 진행해도 아웃이 되지 않는 한 이닝은 계속 진행되므로 9번 선수 다음에는 1번선수가 경기를 하도록 잘 처리해주어야 한다. 마찬가지로 이닝이 끝나도 이닝이 끝날 때 선수의 다음 선수가 바로 이어서 다음 이닝에서 시작할 것이므로 다음 이닝을 시작할 타자의 index를 잘 저장해두어야 한다. (이때도 9번 선수 다음 1번선수가 오는 경우를 잘 처리해줘야 한다!)

이제 가장 중요한 타자가 진루했을 때 점수를 구하는 방법이다.

나는 location이라는 변수를 두고 비트 마스크를 이용하여 풀었다.

location = 0000000

으로 볼 때 각 자리는 다음과 같은 의미를 가지고 있다고 본다.

점수	점수	점수	3루	2루	1루	홈
0	0	0	0	0	0	0

각 타자가 공격을 시작할 때 먼저 location의 값에 1을 더해줘서 홈에 1이 생기도록 해준다.

그리고

안타: location << 1을 해주면 주자들이 왼쪽으로 한 루씩 진루한다.
2루타: location << 2를 해주면 주자들이 왼쪽으로 두 루씩 진루한다.
3루타: location << 3을 해주면 주자들이 왼쪽으로 세 루 씩 진루한다.
홈런: 현재 나와있는 모든 타자들이 모두 홈으로 돌아와서 점수를 얻을 것이므로 현재 홈, 1루, 2루, 3루에 있는 타자 들 만큼 점수를 더해준다.
아웃: 아웃수를 증가해주고 아웃수가 3인 경우에는 다음 이닝을 시작할 타자 인덱스를 저장해 두고 location = 0으로 만들어준다.(새로 시작해야 하기 때문에 나와있는 타자들은 모두 들어온다)

홈런은 위에 쓴 것처럼 바로 점수를 계산해주었고 안타에서 3루타까지는 타자가 공격을 할 때마다 점수를 계산해줘야 하는데 위의 location에서 3루보다 왼쪽으로 넘어간 경우에(홈으로 다시 들어왔다고 볼 수 있음) 점수를 얻게 된다.

한 번에 최대로 3만큼 움직일 수 있으므로(3루타를 친경 우) 1 << 4 에서부터 1 << 5, 1 << 6 한 위치까지만 검사해주면 되는데 해당 자리에 1이 있으면(주자가 있으면) 점수를 더해주면 된다.

점수를 더해줬으면 해당 선수는 나와야 하므로 location에서 해당 선수의 자리를 다시 0으로 만들어주어야 한다.

오른쪽에서부터 i번째 위치의 1을 제거해주기 위해서는

location = location & ~(1 << i);

이런 식으로 & ~ 연산을 해주면 된다.

구체적으로 예를 들어 보자

0001100 인 상태에서 (2루와 3루에 타자가 있음)

홈에 다음 타자가 오면 +1을 해줘서

0001101 이 되고 이 타자가 3루타를 치면

0110100 이 된다.

이때 0110100 빨간 부분의 점수를 계산해주고 1을 없애주면 된다.

이 경우에는 1<<4 일 때

0110100

&0010000

0010000 으로 0이 아닌 값이 나와서 점수를 1 증가시켜준다.

그리고 다시

0110100

&1101111 // ~(1<<4)와 &연산을 해줘서 1을 없애준다.

0100100

마찬가지로 1 << 5일 때도 점수를 더해주고 1을 없애줄 수 있고

1 << 6 인경우는 0이므로 (주자가 없으므로) 계산해주지 않는다.

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

#include <iostream>
#include <vector>
using namespace std;
 
int info[51][10];
bool check[10];
int n;
int ans;
int location;
 
vector<int> order;
 
 
//타자가 진루하였을때의 점수를 계산하여 return
int go() {
 
    int point = 0;
 
    for (int i = 4; i < 7; i++) {
        if (location & (1 << i)) {
            point += 1;
 
            //점수에 더해줬으면 해당 위치의 1을 제거
            location = location & ~(1 << i);
        }
    }
 
    return point;
}
 
 
//경기 시작
int start() {
    int out = 0;
    int point = 0;
    int first = 1;
 
 
    //주자의 위치를 표현할 변수
    location = 0;
 
 
    //이닝수만큼 진행
    for (int i = 1; i <= n; i++) {
 
        //각각의 타자들 공격
        int j = first;
        while (true) {
 
            //j번 타자의 i번째 이닝에서의 점수
            int result = info[i][order[j]];
 
            if (result == 1) {
                location += 1;
                location = location << 1;
                point += go();
            }
            else if (result == 2) {
                location += 1;
                location = location << 2;
                point += go();
            }
            else if (result == 3) {
                location += 1;
                location = location << 3;
                point += go();
            }
            else if (result == 4) {
                location += 1;
                for (int k = 0; k < 4; k++) {
                    if (location & (1 << k)) {
                        point += 1;
                    }
                }
 
                //홈런이므로 모두 나간다
                location = 0;
            }
            else if (result == 0) {
                out++;
 
 
                //3아웃이면 이닝 종료
                if (out == 3) {
                    out = 0;
 
                    //다음 이닝에서 현재 순서의 다음타자부터 시작
                    first = j+1;
                    if (first == 10) first = 1;
 
                    //현재 이닝이 끝났으므로 주자를 모두 없앤다.
                    location = 0;
                    break;
                }
            }
 
 
            //다음타자
            j++;
            if (j == 10) j = 1;
        }
 
 
    }
 
 
 
    //이번에 선택한 타순으로 얻는 득점을 리턴 
    return point;
 
}
 
 
//타순을 정해준다. index번째에 공격할 타자를 정한다.
void select(int index) {
    //9명의 타순을 모두 정한 경우 경기 시작
    if (index > 9) {
        //해당 순서에서 진행한 경기의 점수를 받아와서 최댓값과 비교
        int tmp = start();
        if (ans < tmp) ans = tmp;
        return;
    }
 
 
    //4번타자는 무조건 1번 선수
    if (index == 4) {
        order.push_back(1);
        check[1] = true;
        select(index + 1);
        order.pop_back();
    }
    else {//1번 선수를 제외한 모든 선수를 index번째 순서에 넣어본다.
        for (int i = 2; i <= 9; i++) {
            if (check[i]) continue;
 
            //index번째에 i번 타자를 선택하고 다음 타자를 정해준다.
            order.push_back(i);
            check[i] = true;
            select(index + 1);
 
            //다음 경우를 위해서 false로 바꿔주고 벡터에서 빼준다.
            check[i] = false;
            order.pop_back();
 
        }
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> info[i][j];
        }
    }
 
 
    //1부터 시작할 것이므로 0번째에 자리 채워 준다 (그냥 0 넣어줌)
    order.push_back(0);
 
    //탐색 시작
    select(1);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 15686. 치킨 배달 (0)	2019.08.04
[BOJ] 16234. 인구 이동 (0)	2019.08.02
[BOJ] 17136. 색종이 붙이기 (0)	2019.08.02
[BOJ] 17135. 캐슬 디펜스 (0)	2019.08.01
[BOJ] 16236. 아기 상어 (0)	2019.07.31

[BOJ] 17136. 색종이 붙이기

2019. 8. 2. 15:26

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

17136번: 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐

www.acmicpc.net

10X10 인 종이에 있는 1을 색종이를 사용하여 모두 덮는 문제이다.

종이의 크기가 10X10이고 사용할 수 있는 색종이가 최대 5X5개 이므로 완전 탐색이 가능하다

1이 있는 곳에 대해서 5가지의 색종이를 모두 붙여보고 최솟값을 구해주면 된다.

처음에는 그냥 큰 것부터 붙이면 되는 줄 알고 그렇게 구현했다가 틀렸었다.

큰 종이를 먼저 붙여버려서 애매하게 남은 칸이 발생해서 아예 색종이를 덮지 못하는 경우가 생길 수도 있기 때문이다

내가 구현한 방식은 먼저

배열에서 1인 곳(색종이를 덮어줘야 하는 곳)을 찾는다.
- 없다면 모두 채운 것이므로 현재까지 사용한 색종이의 수를 정답과 비교해주고 return 한다.
- 있다면 반복문을 break 해주고 1인 곳을 5가지의 색종이로 덮는 모든 경우를 해준다.
이제 각각의 색종이로 덮어보는 모든 경우를 해줄 것인데 k*k크기의 색종이로 덮는다고 했을 때, 처리해줘야 할 조건은 다음과 같다
- 해당 크기의 색종이가 남아있는지
- 해당 크기의 색종이로 1인 곳으로부터 k*k칸을 모두 덮을 수 있는지(중간에 0이 없는지)
- 추가적으로 위의 조건에서 10x10의 범위를 넘어가지 않는지도 잘 체크해주어야 한다.
위의 조건들을 통과해서 k*k크기의 색종이를 사용할 수 있다면 색종이 수를 하나 감소해준다.
그리고 k*k 크기만큼 0으로 만들어준다. 이때 새로운 배열을 만들어서 덮어줘야 한다.
- 현재 칸(1인 곳)에 대해서 1x1을 사용하는 경우에서부터 5x5를 사용하는 경우는 모두 다른 결과가 나오기 때문에 각각 새로 만들어서 다음 경우로 보내주어야 한다.
- 즉, 새로 만들어주지 않고 기존의 배열을 사용하면 이미 앞에서 사용한 색종이를 적용한 상태에서 또 덮어버리는 모양이 되기 때문이다.
이제 현재 k*k크기의 색종이로 덮어준 새로운 배열과 함께 사용한 색종이 숫자를 하나 증가시켜서 재귀 호출을 해준다.
재귀 호출에서 돌아온 경우에는 위에서 사용한 색종 이수를 다시 늘려준다. (현재 칸에 대해서 다른 색종이를 사용하는 경우를 해줘야 하기 때문)

(추가) 사용한 색종이 숫자의 최솟값을 찾는 문제이기 때문에 현재 사용한 색종 이수가 정답보다 커질 경우 더 탐색할 필요가 없으므로 43번째 줄에 if(usingnum >= ans) return;를 추가해주면 시간을 더 줄일 수 있다!

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include <iostream>
using namespace std;
 
int papercnt[6];
int ans;
 
void mapcopy(int paper[10][10], int newpaper[10][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            newpaper[i][j] = paper[i][j];
        }
    }
}
 
 
//종이를 k크기만큼 덮는다
void cover(int x, int y, int k, int paper[10][10]) {
    for (int i = x; i < x + k; i++) {
        for (int j = y; j < y + k; j++) {
            paper[i][j] = 0;
        }
    }
}
 
 
//k*k크기의 색종이를 덮을 수 있는지 검사한다. 불가능할 경우 바로 false를 리턴
bool usePaper(int x, int y, int k, int paper[10][10]) {
    for (int i = x; i < x + k; i++) {
        for (int j = y; j < y + k; j++) {
 
            //종이 범위 를 넘어가면 false
            if (i >= 10 || j >= 10) return false;
 
            //0이 있는 자리에는 색종이를 놓을 수 없다
            if (paper[i][j] == 0) return false;
        }
    }
 
    return true;
}
 
void solve(int paper[10][10], int usingnum) {
 
    //색종이가 안덮인 곳을 찾는다.
    bool flag = false;
    int x, y;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (paper[i][j] == 1) {
                x = i;
                y = j;
                flag = true;
                break;
            }
        }
        if (flag) break;
    }
 
 
    //종이를 다 붙였다
    if (!flag) {
        if (ans > usingnum) ans = usingnum;
        return;
    }
 
 
    //각각의 종류의 색종이를 사용하는 경우를 모두 구해준다
    for (int k = 5; k > 0; k--) {
        
        //해당 색종이가 없다
        if (papercnt[k] == 0) continue;
        
        //해당 종이로 채울 수 없다
        if (!usePaper(x, y, k, paper)) continue;
        
        //종이 사용
        papercnt[k] -= 1;
 
        //새로운 배열을 만들고
        int newpaper[10][10];
        mapcopy(paper, newpaper);
 
        //덮는다
        cover(x, y, k, newpaper);
        
 
        //k*k색종이를 사용한 경우에 대해서 새로 탐색을 해준다.
        //색종이 사용 횟수 증가
        solve(newpaper, usingnum+1);
 
        //다른 색종이를 사용하는 경우를 위해서 종이 다시 증가
        papercnt[k] += 1;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int paper[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> paper[i][j];
        }
    }
 
 
    //각 색종이는 처음에 5개씩 있다
    for (int i = 1; i <= 5; i++) papercnt[i] = 5;
 
    //최솟값을 찾기 위해 정답을 최댓값으로 초기화
    ans = 26;
 
    solve(paper, 0);
 
 
    //ans값이 초기값이라면 1을 모두 덮는 것이 불가능한 경우다.
    if (ans == 26) cout << -1 << '\n';
    else cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 16234. 인구 이동 (0)	2019.08.02
[BOJ] 17281. ⚾ (0)	2019.08.02
[BOJ] 17135. 캐슬 디펜스 (0)	2019.08.01
[BOJ] 16236. 아기 상어 (0)	2019.07.31
[BOJ] 17144. 미세먼지 안녕! (0)	2019.07.30

[BOJ] 17135. 캐슬 디펜스

2019. 8. 1. 12:14

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

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

궁수 3명의 위치를 고르기 위해 완전 탐색을 하고 공격할 적을 찾기 위해서 BFS를 사용하였다.

문제에서 주어지는 사정거리를 계산하는 식이 딱 BFS 모양이기 때문이다.

적당히 잘 계산해주면 BFS를 사용하지 않아도 되긴 한다(처음에 이렇게 풀었었다)

먼저 배열은 궁수의 위치 때문에 행의 크기를 하나 더 크게 해주어야 한다.

n과 m의 범위가 최대 15이므로 배열의 범위는 16x15로 해주면 된다.

배열을 입력받았다면 n행의 궁수의 위치(y좌표)를 고르는 경우를 모두 구해준다.

0부터 m까지의 y좌표에서 해당 위치를 선택하는 경우와 안 하는 경우를 모두 구해주고,

3명의 위치를 모두 골라줬다면 공격을 시작한다.

공격을 시작할 때 주의할 점은 배열을 새로 만들어서 공격을 시작해야 한다.

궁수의 위치를 다시 골라줬을 때 처음 상태에서 다시 시작해야 하기 때문이다.

그러고 나서는 적이 모두 사라질 때까지 세명의 궁수의 공격과 적군의 이동을 반복하고

적군이 모두 사라졌을 때까지의 점수를 최댓값과 비교하여 저장한다.

공격할 적을 찾기 위해 bfs탐색을 하는데 각 궁수의 위치에서부터 시작해준다.

이전의 아기 상어 문제와 비슷하게 큐 사이즈를 저장해놨다가 큐 사이즈만큼을 먼저 진행하면

단계별로 bfs를 진행해줄 수 있다.

즉, 사정거리가 1 씩 증가할 때마다 적군을 찾았는지 확인하고 d(문제에서 주어진 사정거리) 보다 작은지 확인할 수 있다.

해당 궁수의 bfs탐색에서 적군을 공격했거나, 사정거리를 넘어갈 때까지 적군을 찾지 못한 경우에는

탐색을 중단하고 다음 궁수의 bfs탐색을 진행한다.

적군을 찾은 경우에는 배열에 따로 죽은 적군의 좌표를 저장해두었다. 궁수들이 같은 적을 죽일 수도 있기 때문에

점수를 바로바로 계산해줄 수 없기 때문이다.

3명의 궁수에 대한 적군 탐색이 끝났다면 위에서 저장해둔 죽은 적군들의 좌표를 검사해서 점수를 계산한 후 리턴한다.

한 번의 공격 턴이 끝났다면 적군들을 한 칸씩 아래로 내려주면 된다.

더 자세한 설명은 코드 참고!

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m, d;
int ans;
int firstmap[16][15];
int map[16][15];
 
int dx[] = { -1,0,0 };
int dy[] = { 0,-1,1 };
 
//궁수의 y좌표를 저장
vector<int> archer;
//궁수가 공격할 적을 탐색할 때 방문 체크할 배열
bool check[16][15];
//죽은 적을 체크
bool isdead[15][15];
 
 
//처음에 입력받은 배열을 복사
void mapcopy() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = firstmap[i][j];
        }
    }
}
 
 
//적이 모두 죽었는지 검사
bool isover() {
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 1) return false;
        }
    }
 
    return true;
}
 
 
//적군의 이동
void move() {
    //맨 밑칸부터 바로 윗칸의 적들을 내려준다.
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < m; j++) {
            map[i][j] = map[i - 1][j];
        }
    }
 
    //맨 윗줄은 모두 0으로 넣어준다
    for (int j = 0; j < m; j++) {
        map[0][j] = 0;
    }
}
 
 
//점수 계산
int calc() {
    int point = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //죽은 애들이 있을 때 point 증가
            if (isdead[i][j]) {
                point++;
                
                //죽은 곳 0으로 바꿔줌
                map[i][j] = 0;
            }
 
            //궁수는 3명이므로 한번의 턴에서 얻을 수 있는 최대 점수는 3점이므로 3점이 되면 바로 return
            if (point == 3) return point;
        }
    }
 
    //점수를 리턴
    return point;
}
 
 
//공격
int bfs() {
    //새로 궁수를 배치한 경우가 시작되므로 죽은 애들 체크하는 배열을 reset
    memset(isdead, false, sizeof(isdead));
    int point = 0;
 
    
    //궁수 3명에 대해서 각각 bfs탐색을 해준다.
    for (int i = 0; i < 3; i++) {
        queue<pair<int, int>> q;
        memset(check, false, sizeof(check));
 
        int y = archer[i];
        q.push(make_pair(n, y));
        check[n][y] = true;
 
        int qsize;
        int killx = 100;
        int killy = 100;
 
        int dist = 0;
        while (!q.empty()) {
            dist++;
 
            //현재 거리가 사정거리를 넘어가면 break
            if (dist > d) break;
            qsize = q.size();
 
 
            //사정거리까지의 단계별 진행을 위해서 큐사이즈만큼 진행한다.
            while (qsize-- > 0) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
 
                //위,왼,오 방향으로 이동(아래로는 갈 필요 없다)
                for (int k = 0; k < 3; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
 
                    //범위 체크
                    if (nx < 0 || ny < 0 || ny >= m) continue;
                    //방문 체크
                    if (check[nx][ny]) continue;
                    
                    
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
 
 
                    //적군이 있다
                    if (map[nx][ny] == 1) {
                        //더 왼쪽에 있는 애를 죽일거다
                        if (ny < killy) {
                            killx = nx;
                            killy = ny;
                        }
                    }
                }
 
 
            }
 
            //이번 턴에서 적군을 발견했다.
            if (killx != 100) {
                //죽이는 걸로 체크
                isdead[killx][killy] = true;
                
                //i번째 궁수는 죽일 적을 찾았으므로 탐색을 중단한다.
                break;
            }
        }
    }
 
 
    //이번 턴에서 얻은 점수를 계산
    point = calc();
 
 
 
    return point;
}
 
void select(int index, int cnt) {
    //궁수의 위치를 모두 정했다.
    if (cnt == 3) {
        int point = 0;
 
        //이번에 정한 궁수의 위치에서 공격할 배열을 새로 만들어준다.
        mapcopy();
 
        //모든 적이 죽을 때까지 반복
        while (!isover()) {
            //이번 시간의 공격에서의 점수
            point += bfs();
 
            //이동
            move();
        }
 
        //점수를 최댓값과 비교
        if (ans < point) ans = point;
 
        return;
    }
    if (index >= m) return;
 
 
    //index번째 열에 궁수를 배치
    archer.push_back(index);
    select(index + 1, cnt + 1);
 
 
    //index번째 열에 궁수를 배치하지 않는다.
    archer.pop_back();
    select(index + 1, cnt);
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> firstmap[i][j];
        }
    }
 
    select(0, 0);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17281. ⚾ (0)	2019.08.02
[BOJ] 17136. 색종이 붙이기 (0)	2019.08.02
[BOJ] 16236. 아기 상어 (0)	2019.07.31
[BOJ] 17144. 미세먼지 안녕! (0)	2019.07.30
[BOJ] 17140. 이차원 배열과 연산 (0)	2019.07.30

PREV 1 2 3 4 5 NEXT

알고리즘매일매일