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


조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.


다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.




알고리즘은 다음과 같다.


1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.


2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.


3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.


4. 수정한 map과 방문처리 배열을 초기화 시켜준다.



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
//map에 1을 세개 두고, 만들 수 있는 0의 최대 개수
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int R, C, m[9][9], arr[4];//빈공간 담은 벡터의 인덱스 저장
vector<pair<int, int> > v; //빈공간 저장 벡터
bool vis[9][9], isused[81];
int res = 0, st = 0;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void bfs(pair<int, int> start) {
    q.push({ start.first, start.second });
    vis[start.first][start.second] = true;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (vis[nr][nc] || m[nr][nc] == 1) continue;
 
            q.push({ nr, nc });
            vis[nr][nc] = true;
        }
    }
}
void findSafe() {
    int cnt = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (!vis[i][j] && m[i][j] == 0) cnt++; //빈칸이면서 바이러스가 퍼지지 않은 곳 = 안전지점
 
    if (res < cnt)
        res = cnt;
}
void init() {
    for (int i = 0; i < 3; i++) {
        int j = arr[i];
        m[v[j].first][v[j].second] = 0; //벽 세웠던 부분 다시 빈칸으로
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            vis[i][j] = false;
        }
    }
}
void backTracking(int k) {
    if (k == 3) { //빈공간 중에서 세개 조합 뽑아서
        for (int i = 0; i < 3; i++) {
            int j = arr[i];
            m[v[j].first][v[j].second] = 1; //1로 바꿔주고
        }
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j] == 2 && !vis[i][j]) bfs({ i, j }); //bfs 실행
            }
        }
 
        findSafe(); //빈칸이면서 방문되지 않은 지점 검색
 
        init(); //map, vis 수정한 값 초기화
 
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            if (m[i][j] == 0) v.push_back({ i, j }); //빈공간 인덱스 미리 저장
        }
    }
 
    backTracking(0); //빈공간 인덱스 조합 검사
 
    cout << res;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05
백준 17141번: 연구소 2 (C++)  (0) 2019.08.05

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



특별한 알고리즘이랄 것이 필요하지 않은 전형적인 시뮬레이션 문제였다.


하지만 설계를 제대로 하고 들어가지 않으면 꽤 해맬 수 있었던 문제이다.



여느 시뮬레이션 문제들이 그러하듯이, 상황을 어떻게 표현할 것인가 생각해야 한다.


나는 주의 깊게 그림을 살펴보지 않아서 간과했던 사실이지만, 문제 설명에서 그림을 보여주면서 좌표 값을 그림 아래에 표시해줬다.



그것을 보면, 커브의 상태를 좌표에 찍을 수 있고, 좌표에 어떻게 찍히느냐는 기본적으로 세대가 결정하고,


같은 세대라고 할지라도 시작한 방향값이 다르다면 다르게 찍힌다는 것을 알 수 있다.



(0,0)에서 시작한 0세대 커브는 (1,0)으로 x값이 1증가한다.


그리고 이어서 2세대로 변천할 때, 1세대의 마지막 점(1,0)에서 (1,-1)로 이동하여 y좌표가 1감소하는 것을 알 수 있다.


이 상황은 0,0에서 시작한 d값이 1인 0세대의 커브이다.


만약 나머지 조건이 동일하고, 방향 값인 d값이 1이었다면?  0,0에서 시작한 커브는 상단으로 뻗었을 것이고


0세대 커브는 0,0에서 0,-1로 변천했을 것이다. 이런식으로 파악해나가야 한다.



방향이 0인 세대별 커브의 성분을 방향 숫자로 나타내보면,


0세대: 0


1세대: 0, 1


2세대: 0, 1, 2, 1


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


4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1


...


이런식으로 증가한다. 여기서 규칙을 확인할 수 있다. 먼저 개수가 2의 거듭제곱 꼴로 늘어나고 있다.


그리고 문제에서 주어진 조건과 연결해서 확인해보면, 이전 세대의 커브를 90도 돌리고 끝을 붙인다고 했다.


90도 돌린다는 것은 방향값의 변화를 의미하는 것이고, 끝을 붙인다는 것은, 성분을 뒤에서부터 하나씩 붙인다는 것이다.


따라서 0세대에서 1세대로 갈 때, 0에 1을 더한 1이 붙은 것이고, 1세대에서 2세대로 갈 때, 1세대의 마지막인 1에 1을 더한 값인 2가 붙고, 0에 1을 더한 값인 1이 그 뒤에 붙은 것이다.


이를 그냥 배열 인덱스로 조절해서 구해도 되겠지만 동작 구조가 스택과 같으니, 스택을 활용했다.



나는 방향 0의 드래곤커브의 10세대를 구해서 배열에 저장했다. 10세대를 구하면 곧, 앞부분에 0~9세대도 포함되어 있는 것이기 때문에 변형해서 사용하면 된다. 또한 방향 0의 값을 구해 놓았으니, 방향이 변하면 모든 성분을 더해줘서 방향을 바뀐 것처럼 사용하면 되고, %4를 통해 값이 4를 넘어가지 않도록 유지해줘야 하겠다.




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
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
stack<int> stk;
int map[101][101];
int d[1025]; //0~3방향, 0~10세대
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j <= (1 << (i - 1)) - 1; j++) {
            stk.push(d[j]); //이전 세대의 것을 스택에 넣고
        }
        for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) {
            d[j] = (stk.top() + 1) % 4;
            stk.pop();
            //1씩 증가하면서 pop하면서 이전 세대의 것에 붙이면 현재 세대의 것이 나옴
        }
    }
 
    for (int i = 0; i < n; i++) {
        int x, y, dir, gen;
        cin >> x >> y >> dir >> gen;
        map[y][x] = 1;
        for (int j = 0; j <= (1 << gen) - 1; j++) {
            if ((d[j] + dir) % 4 == 0) {
                x++; //갱신하면서 움직여야 반영됨
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 1) {
                y--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 2) {
                x--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 3) {
                y++;
                map[y][x] = 1;
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < 100; i++) { //생각 없이 n까지만 잡으면 안 되고, x, y 최대 범위만큼
        for (int j = 0; j < 100; j++) { 
            if (map[i][j] == 1 && map[i][j + 1] == 1 &&
                map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) cnt++;
        }
    }
    cout << cnt;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05
백준 17141번: 연구소 2 (C++)  (0) 2019.08.05
백준 11050번: 이항 계수1 (C++)  (0) 2019.08.05

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



비교적 간단한 조합 / 백트래킹 / 전수조사 문제이다.



문제를 보면, 결국 모든 경우의 수를 조사해야 하는 상황이다. 따라서 집의 위치와, 치킨집의 위치를 따로 벡터에 담아주고,


백트래킹을 활용해서 치킨집을 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
#include<iostream>
#include<vector>
#include<math.h>
#include<limits.h>

using namespace std;
int map[52][52], n, m, st = 0, arr[14];
 
vector<pair<int, int > > v, hv; //치킨집, 가정집
 
int res = INT_MAX;
bool isused[14];
void process() {//집마다 치킨집 여러개와의 거리가 있는데, 그 거리의 최소값의 합을 구한다
    int cityDis = 0;

    for (int i = 0; i < hv.size(); i++) {
        int Min = INT_MAX;
        for (int j = 0; j < m; j++) {
            int sumR = 0, sumC = 0;
            sumR += abs(hv[i].first - v[arr[j]].first);
            sumC += abs(hv[i].second - v[arr[j]].second);
            if (sumR + sumC < Min) Min = sumR + sumC;
        }
        cityDis += Min; //도시의 치킨거리
    }

    if (res > cityDis) res = cityDis; //도시의 치킨거리 최댓값 갱신 
}

void backTracking(int k) { //조합 템플릿
    if (k == m) {
        //arr에 치킨벡터 인덱스
        process();
        return;
    }

    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}

int main(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) v.push_back({ i, j }); //치킨집
            else if (map[i][j] == 1) hv.push_back({ i, j }); //가정집
        }
    }
    
    backTracking(0);
 
    cout << res << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 17141번: 연구소 2 (C++)  (0) 2019.08.05
백준 11050번: 이항 계수1 (C++)  (0) 2019.08.05
백준 17142번: 연구소 3 (C++)  (0) 2019.08.05

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



연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.


기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.


바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.




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
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;
int map[51][51], n, m, dis[51][51], st = 0, arr[11];
vector<pair<int, int> > v;
bool isused[11];
queue<pair<int, int> >q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;
 
void init() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = -1;
}
 
pair<bool, int> check() {
    int Max = -2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] == -1 && map[i][j] == 0) return { false, -2 };
            if (Max < dis[i][j]) Max = dis[i][j];
        }
    }
    return { true, Max }; //바이러스가 완전히 확산된 경우만 시간 반환
}
 
void bfs() {
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nr >= n) continue;
            if (map[nr][nc] == 1 || dis[nr][nc] >= 0) continue;
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
    if (check().first) {
        int rtn = check().second;
        if (rtn < res) res = rtn; //반환된 시간의 최솟값 갱신
    }
}
void backTracking(int k) {
    if (k == m) {
        for (int i = 0; i < m; i++) {
            //arr에 바이러스의 인덱스를 저장
            q.push({ v[arr[i]].first, v[arr[i]].second });
            dis[v[arr[i]].first][v[arr[i]].second]++;
        }
        bfs();
 
        init(); //dis 초기화
        
        return;
    }
    if (k == 0) st = 0; //조합 템플릿
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            isused[i] = true;
            st = i;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) v.push_back({ i, j });
        }
    }
    init();
 
    backTracking(0);
 
    if (res != INT_MAX) cout << res; //결과가 갱신된적이 없다면 제대로 확산된 적이 없는 것
    else
        cout << -1;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05
백준 11050번: 이항 계수1 (C++)  (0) 2019.08.05
백준 17142번: 연구소 3 (C++)  (0) 2019.08.05
백준 17143번: 낚시왕 (C++)  (0) 2019.08.04

문제 링크: https://www.acmicpc.net/problem/11050


n과 k가 주어질 때, nCk를 구하면 되는 문제이다.


팩토리얼 계산을 통해서 구현하면 된다.


팩토리얼을 통한 구현은, n이 15만 되더라도 int의 범위 근처이고, 21까지만 되도 long long의 범위 근처이기 때문에, 이 문제처럼 n이 10으로 작을 경우에만 사용한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
typedef long long ll;
int main(void) {
    ll n, k;
    cin >> n >> k;
    
    ll son = 1, mom = 1;
    for (int i = 0; i < k; i++) 
        son = son * (n - i);
 
    for (int i = 0; i < k; i++) 
        mom = mom * (k - i);
 
    cout << son / mom;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05
백준 17141번: 연구소 2 (C++)  (0) 2019.08.05
백준 17142번: 연구소 3 (C++)  (0) 2019.08.05
백준 17143번: 낚시왕 (C++)  (0) 2019.08.04
백준 16235번: 나무 재테크 (C++)  (0) 2019.07.30

+ Recent posts

티스토리툴바