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

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

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

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

(추가) 사용한 색종이 숫자의 최솟값을 찾는 문제이기 때문에 현재 사용한 색종 이수가 정답보다 커질 경우 더 탐색할 필요가 없으므로 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

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

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

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크

www.acmicpc.net

처음에 입력받을 때 아기 상어의 위치에 값이 9가 들어가 있는데, 아기 상어의 좌표를 큐에 넣어줬으면 값을 다시 0으로 바꿔주는 것이 좋다.

아기 상어의 원래 위치를 몸집이 9인 물고기로 생각하고 이동을 못할 수도 있기 때문이다.

물론 이렇게 안 해주고 이동할 때 0에서 6으로 정확히 조건을 처리해줘도 상관없다.

 

문제에 나와있는 다음과 같은 조건에 따라 아기 상어를 이동시키며 물고기를 잡아먹으면 된다.

 

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

아기 상어의 이동은 bfs를 이용하고 가장 가까운 거리에서 먹을 수 있는 물고기들을 비교하기 위해서는 큐사이즈 만큼(같은 거리)만 먼저 진행하여 단계별로 진행하도록 하였다. 같은 단계 안에서 먹을 수 있는 물고기들이 있다면 더 위쪽에 있고 더 왼쪽에 있는 물고기의 위치를 저장해 놓는다. 즉, x좌표가 더 작고 그다음으로 y좌표가 더 작은 경우이므로 잡아먹을 물고기의 좌표를 초기값으로 큰 값을 넣어둔 후 물고기의 위치가 더 작은 값이라면 변경해준다.

 

 

현재 단계의 탐색이 끝났다면 잡아 먹을 물고기가 있었는지 확인한다. 잡아 먹을 물고기의 좌표가 변해있다면 있는 것이다. 그러면 잡아먹을 물고기의 좌표로 이동 후에 바로 잡아먹는다. 문제 조건에 따라먹을 때마다 먹은 수를 증가시키고 아기 상어의 크기와 비교해주어야 한다.

 

 

잡아먹은 후에는 큐를 비워준 후 큐에 아기 상어의 위치를 새로 넣어주고 다시 탐색을 시작하면 된다. 이때 방문을 체크하는 배열도 같이 초기화해주어야 한다.

 

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

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n,shark, ans;
int map[20][20];
int visit[20][20];
 
int dx[] = {0,0,1,-1};
int dy[] = { 1,-1,0,0 };
 
queue<pair<int, int>> q;
 
void solve() {
 
 
    int x, y;
 
    //잡아먹을 물고기의 좌표
    int movex = 100, movey = 100;
 
    //먹은 물고기 수
    int eatcnt = 0;
 
    while (!q.empty()) {
        int qsize = q.size();
 
        //큐의 사이즈만큼만 진행하면서 단계별로(시간별로) 진행할 수 있다.
        while (qsize-- > 0) {
            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 (visit[nx][ny]) continue;
                //아기상어보다 크기가 크면 못지나간다.
                if (map[nx][ny] > shark) continue;
 
                //이동할 곳을 큐에 넣고 시간을 체크
                q.push(make_pair(nx, ny));
                visit[nx][ny] = visit[x][y] + 1;
 
                //먹을 수 있는 물고기가 있다. (크기가 아기상어보다 작고 빈칸은 아니다)
                if (map[nx][ny] != 0 && map[nx][ny] < shark) {
                    //먹을 수 있는 물고기중 더 위쪽의 물고기를 먹는다.
                    if (movex > nx) {
                        movex = nx;
                        movey = ny;
                    }
                    else if (movex == nx) { //똑같이 위쪽에 있다면 더 왼쪽에 있는 물고기를 먹는다.
                        if (movey > ny) {
                            movex = nx;
                            movey = ny;
                        }
                    }
                }
            }
        }
 
 
        //먹은 물고기가 있다. (먹을 물고기의 좌표가 초기값이 아니다)
        if (movex != 100) {
 
            //먹은 물고기수 증가
            eatcnt++;
 
            //먹은 물고기 수가 아기상어의 크기와 같아졌다면 아기상어의 크기 증가, 먹은 물고기 수는 초기화
            if (eatcnt == shark) {
                shark++;
                eatcnt = 0;
            }
 
            //잡아먹으므로 값 0으로 바꿔줌
            map[movex][movey] = 0;
 
            //현재 위치까지의 시간을 따로 저장해놓는다.
            int time = visit[movex][movey];
 
            //현재 위치에서 새로 탐색을 시작하기 위해서 기존의 큐는 모두 비워준다.
            while (!q.empty()) q.pop();
            //시간을 체크한 visist배열도 초기화
            memset(visit, 0, sizeof(visit));
 
 
            //아기상어의 새로운 위치를 새로 큐에 추가하고 아까 저장해놓은 시간을 visit배열에 저장
            q.push(make_pair(movex, movey));
            visit[movex][movey] = time;
 
            //마지막으로 물고기를 먹었을 때의 시간을 저장
            ans = time;
 
            //먹을 물고기 위치 초기화
            movex = 100;
            movey = 100;
        }
 
    }
    
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
 
            //아기상어인 경우 큐에 추가 및 시간 0으로 표시
            if (map[i][j] == 9) {
                q.push(make_pair(i, j));
                visit[i][j] = 0;
 
                //나중에 아기상어가 다시 지나갈 수 있도록 0으로 바꿔준다.
                map[i][j] = 0;
            }
        }
    }
 
    //상어 초기 크기
    shark = 2;
    solve();
    
 
    cout << ans << '\n';
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17136. 색종이 붙이기  (0) 2019.08.02
[BOJ] 17135. 캐슬 디펜스  (0) 2019.08.01
[BOJ] 17144. 미세먼지 안녕!  (0) 2019.07.30
[BOJ] 17140. 이차원 배열과 연산  (0) 2019.07.30
[BOJ] 17142. 연구소 3  (0) 2019.07.30

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼

www.acmicpc.net

처음에 큐를 사용하지 않고 벡터로 구현을 했어서 헤맸던 문제였다...

공기청정기 바람 나오는 거 구현할 때에도 범위 때문에 계속 헷갈렸었다

공기청정기는 위쪽과 아래쪽을 나눠서 각각 구현해줬다. 그냥 문제에서 시키는 대로 한 칸씩 이동시켜주면 된다.

 

미세먼지 확산의 경우에는 확산되는 먼지는 따로 저장해서 나중에 한번에 더해줘야 한다.

바로 더해주면 확산된 곳에서 같은 시간에 다시 확산될 수 도 있기 때문이다

이 부분이랑 공기청정기에서 바람 나와서 이동할 때 범위만 조심해주면 될 것 같다!

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
int R, C, T;
int map[50][50];
int sum[50][50];
int air[2];
 
int dx[] = { 0,-1,0,1 };
int dy[] = { 1,0,-1,0 };
 
void goUpair() {
    int x, y;
    x = air[0] - 1;
    y = 0;
 
    if (x < 0) return;
 
    while (x > 0) {
        map[x][y] = map[x - 1][y];
        x--;
    }
    while (y < C - 1) {
        map[x][y] = map[x][y + 1];
        y++;
    }
    while (x < air[0]) {
        map[x][y] = map[x + 1][y];
        x++;
    }
    while (y > 1) {
        map[x][y] = map[x][y - 1];
        y--;
    }
    map[x][1] = 0;
 
}
 
void goDownair() {
    int x, y;
    x = air[1] + 1;
    y = 0;
 
    if (x >= R) return;
 
    while (x < R - 1) {
        map[x][y] = map[x + 1][y];
        x++;
    }
    while (y < C - 1) {
        map[x][y] = map[x][y + 1];
        y++;
    }
    while (x > air[1]) {
        map[x][y] = map[x - 1][y];
        x--;
    }
    while (y > 1) {
        map[x][y] = map[x][y - 1];
        y--;
    }
    map[x][1] = 0;
}
 
void spread() {
    queue<pair<int, int>> q;
 
    //먼지가 있는 곳을 모두 큐에 넣어준다.
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] > 0) {
                q.push(make_pair(i, j));
            }
        }
    }
 
 
    int x, y;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        int amt = map[x][y] / 5;
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (map[nx][ny] == -1) continue;
 
            //확산될때 원래자리에서는 빼주고
            //확산될 자리에서는 더해준다.
            map[x][y] -= amt;
            sum[nx][ny] += amt;
        }
    }
 
    //확산된 먼지들을 더해준다.
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            map[i][j] += sum[i][j];
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> R >> C >> T;
 
    bool flag = true;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) {
                if (flag) {
                    //첫번째 공기청정기
                    air[0] = i;
                    flag = false;
                }
                else {
                    //두번째 공기청정기
                    air[1] = i;
                }
            }
        }
    }
 
 
    //T초 동안 확산과 공기청정(위쪽, 아래쪽)을 반복
    for (int i = 0; i < T; i++) {
        memset(sum, 0, sizeof(sum));
        spread();
        goUpair();
        goDownair();
    }
 
 
    //남아있는 먼지 수를 계산
    int ans = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            ans += map[i][j];
        }
    }
 
 
    //공기청정기 2개때문에 빠진 값을 다시 더해준다.
    cout << ans + 2 << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17135. 캐슬 디펜스  (0) 2019.08.01
[BOJ] 16236. 아기 상어  (0) 2019.07.31
[BOJ] 17140. 이차원 배열과 연산  (0) 2019.07.30
[BOJ] 17142. 연구소 3  (0) 2019.07.30
[BOJ] 1806. 부분합  (0) 2019.07.16

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

 

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

초기 배열의 크기가 3X3이고 1초가 지날 때마다 배열에 연산이 적용되는데

최종적으로 배열의 r행c열에 들어있는 값이 k가 되는 시간을 찾는 문제이다.

시간이 100을 넘어가는 경우에는 -1을 출력한다.

 

R연산과 C연산은 다음과 같다.

  • R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
  • C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

 

이 문제에서 중요한 부분은 각 숫자의 등장 횟수를 센다음에 어떻게 새로 저장해 주느냐인 것 같다.

나는 벡터를 이용해서 저장했다. 벡터의 자료 형을 pair로 넣고 정렬할 경우

pair 중 앞부분 우선으로 먼저 정렬되고 그다음에 두 번째 걸로 정렬되는 점을 이용했다.

 

이 문제에서는 먼저 수의 등장 횟수순으로 정렬되어야 하기 때문에 등장 횟수를 앞에 넣어주고 수를

뒤에 넣어주었다. 그리고 다시 배열에 저장할때는 벡터의 뒤에 거를 먼저 빼서 넣어주고 앞에 거를 넣어줬다.

 

그리고 또 중요한 것은 바뀌는 행의 크기와 열의 크기이다.

매번 연산때마다 크기는 줄어들거나 커질 수 있는데 해당 연산에서의 최댓값으로 다시 갱신해주어야 한다.

 

 

자세한 설명은 코드의 R연산(rcalc) 부분을 참고!

C연산은 R연산을 열 기준으로 바꿔주면 되므로 생략했다.

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int map[150][150];
int cnt[101];
int r, c, k;
int rsize, csize;
vector<pair<int, int>> vt;
 
void c_calc() {
    int new_rsize = 0;
    for (int i = 0; i < csize; i++) {
 
        for (int j = 0; j < rsize; j++) {
            cnt[map[j][i]]++;
        }
 
        for (int k = 1; k <= 100; k++) {
            if (cnt[k] != 0) {
                vt.push_back(make_pair(cnt[k], k));
                cnt[k] = 0;
            }
        }
 
        sort(vt.begin(), vt.end());
 
 
        int vtsize = vt.size();
        int newsize = vtsize * 2;
        new_rsize = max(new_rsize, newsize);
        int index = 0;
        for (int k = 0; k < newsize; k += 2) {
            map[k][i] = vt.at(index).second;
            map[k + 1][i] = vt.at(index).first;
            index++;
        }
 
        for (int k = newsize; k < rsize; k++) {
            map[k][i] = 0;
        }
 
 
        vt.clear();
    }
 
    rsize = new_rsize;
}
 
 
void rcalc() {
 
    int new_csize = 0; //이번 연산에서 새로 바뀔 열 크기 중 최댓값이 저장된다.
 
    //모든 행에 대해서 R연산을 해준다.
    for (int i = 0; i < rsize; i++) {
 
        //숫자의 등장 횟수를 세기 위해서, 각 열의 숫자를 인덱스로 cnt배열의 값을 증가시킨다.
        for (int j = 0; j < csize; j++) {
            cnt[map[i][j]]++;
        }
 
 
        //개수가 0개가 아니라면 벡터에 넣어주고 cnt배열은 다시 0으로 초기화 해준다.
        for (int k = 1; k <= 100; k++) {
            if (cnt[k] != 0) {
 
                //수의 등장횟수로 먼저 정렬되므로 수의 등장횟수를 앞에 넣어주고
                //해당 수를 뒤에 넣어준다.
                vt.push_back(make_pair(cnt[k], k));
                cnt[k] = 0;
            }
        }
 
 
        //정렬
        sort(vt.begin(), vt.end());
 
 
        //쌍으로 벡터에 들어가있으므로 하나씩 꺼내주기 위해 2를 곱해준다.
        int vtsize = vt.size();
        int newsize = vtsize * 2;
 
        //현재 연산의 최대 열 길이(new_csize가 이번 연산이 끝나면 csize(열 사이즈)로 바뀐다)
        new_csize = max(new_csize, newsize);
 
 
        //map에 다시 넣어준다.
        int index = 0;
        for (int k = 0; k < newsize; k += 2) {
            //수를 뒤에 넣었으므로 두번째 값(second)을 먼저 꺼낸다.
            map[i][k] = vt.at(index).second;
 
            //수의 등장 횟수를 앞(first)에 넣어놨으므로 나중에 꺼낸다. 
            map[i][k + 1] = vt.at(index).first;
            index++;
        }
 
        //숫자를 채우고 남은 칸을 0으로 채워준다. (열 크기까지)
        for (int k = newsize; k < csize; k++) {
            map[i][k] = 0;
        }
 
 
        //벡터 정리
        vt.clear();
    }
 
    //열 크기는 이번 연산에서 가장 긴 열의 크기로 바뀐다
    //(줄어들 수 도 있고 늘어날 수 도 있음)
    csize = new_csize;
 
}
 
 
void solve() {
    int time = 0;
    while (true) {
 
        //찾은 경우
        if (map[r][c] == k) {
            cout << time << '\n';
            break;
        }
 
        time++;
 
        //시간이 100을 넘어가는 경우
        if (time > 100) {
            cout << -1 << '\n';
            break;
        }
 
        //R연산
        if (rsize >= csize) {
            rcalc();
        }
        else {//C연산
            c_calc();
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c >> k;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> map[i][j];
        }
    }
 
    //index가 0번부터 시작하므로 1씩 빼준다.
    r--;
    c--;
 
    rsize = 3;
    csize = 3;
 
    solve();
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 16236. 아기 상어  (0) 2019.07.31
[BOJ] 17144. 미세먼지 안녕!  (0) 2019.07.30
[BOJ] 17142. 연구소 3  (0) 2019.07.30
[BOJ] 1806. 부분합  (0) 2019.07.16
[BOJ] 2003. 수들의 합 2  (0) 2019.07.15

+ Recent posts

티스토리툴바