문제 출처:

https://programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

 

조합, map을 이용해서 풀이할 수 있다.

코스요리를 이루는 메뉴의 개수가 곧 조합으로 뽑아야 할 개수에 해당하기 때문에, 뽑아주고, 2명이상의 사람에게 가장 많이 뽑힌 메뉴들을 개수별로 벡터에 저장하고, 오름차순으로 사전순 정렬을 해주면 된다.

 

 

 

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
#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
vector<string> solution(vector<string> ord, vector<int> crs) {
    vector<string> ans;
    for(int i = 0 ; i < crs.size() ; i++){
        int cnt = crs[i];
        for(int j = 0 ; j < ord.size() ; j++){
            
            string curOrd = ord[j];
            sort(curOrd.begin(), curOrd.end());
            if(curOrd.length() < cnt) continue;
            
            vector<int> tmp;
            for(int k = 0 ; k < cnt ; k++){
                tmp.push_back(0);
            }
            for(int k = cnt ; k < curOrd.length() ; k++){
                tmp.push_back(1);
            }
            
            do{
                string str ="";
                for(int k = 0 ; k < curOrd.size() ; k++){
                   
                    if(tmp[k] == 0){
                        str += curOrd[k];
                    }
                }
                if(mp.find(str) == mp.end()){
                    // map에 없으면
                    mp.insert({str, 1});
                }
                else{
                    mp[str]++;
                }
            }while(next_permutation(tmp.begin(), tmp.end()));
        }
        // cur개의 메뉴를 뽑을때, 최대 빈도수로 등장한 메뉴조합
        int maxCnt = 1;
        
        for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
            // cout << itr->first << " = " << itr->second << '\n';
            if(itr->second > maxCnt){
                maxCnt = itr->second;
            }
        }
        if(maxCnt == 1) continue;
        for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
            if(itr->second == maxCnt){
                ans.push_back(itr->first);
            }
        }
        mp.clear();
    }
    
    sort(ans.begin(), ans.end());
    return ans;
}
 cs
저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: N개의 최소공배수(C++)  (0) 2021.10.06
프로그래머스: 뉴스 클러스터링(C++)  (0) 2021.10.06
프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 단어 변환 (C++)  (0) 2019.09.29
프로그래머스: 네트워크 (C++)  (0) 2019.09.28

https://swexpertacademy.com/main/code/problem/problemList.do?problemTitle=SW&orderBy=PASS_RATE&select-1=&pageSize=10&pageIndex=1#none



음식 하나에 들어가는 재료는 n/2개이다. 조합을 이용해서 음식 하나에 들어갈 수 있는 재료를 뽑는다.


여기서 뽑힌 재료가 음식 하나에 들어가는 재료가 되는 것이고, 뽑히지 않은 재료는 나머지 음식에  들어가는 재료가 된다.



뽑은 재료들 사이에 시너지를 계산하기 위해서, 순열로 2개를 뽑는다.


나머지 음식에 대해서도 시너지를 계산해준다.



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
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define INF 987654321
 
int Min = INF;
int food[18][18], arr[2];
int st = 1, n;
bool used[18], usedP[18];
 
vector<int> candi, others;
int Sum = 0;
 
void per(int K, vector<int>& useable) {
    if (K == 2) {
        Sum += food[arr[0]][arr[1]]; //실제로 시너지 계산하는 부분
        return;
    }
    
    for (int i = 0; i < useable.size(); i++) {
        if (!usedP[i]) {
            arr[K] = useable[i];
            usedP[i] = true;
            per(K + 1, useable);
            usedP[i] = false;
        }
    }
}
void com(int k, int goal) {
    if (k == goal) { //n/2개 뽑으면
 
        ////candi에서 2개 순열로 뽑아서 시너지 계산
        Sum = 0;
        per(0, candi);
        int sumA = Sum;
        
        
        //다른 음식에 쓰이는 재료도 마찬가지로 시너지 계산
        others.clear();
        for (int i = 1; i <= n; i++) 
            if (!used[i]) others.push_back(i);
        
 
        Sum = 0;
        per(0, others);
        int sumB = Sum;
 
        int dif = abs(sumA - sumB);
        if (dif < Min) Min = dif; //맛의 차이 업데이트
 
        return;
    }
 
    if (k == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            candi.push_back(i); //음식 하나에 쓰일 재료에 추가
            com(k + 1, goal);
            used[i] = false;
            candi.pop_back();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> food[i][j];
        
        com(0, n / 2); //절반을 조합으로 뽑는다(음식 하나에 쓰일 재료 선택)
 
        cout << "#" << tc << ' ' << Min << '\n';
        Min = INF;
        candi.clear();
        
    }
 
    return 0;
}
 
 
cs



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

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

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



선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다.



따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다.


단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다.




구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다.


우선 n <= 10 으로 작기 때문에 2차원 bool 배열에 구역의 연결 관계를 인접행렬로 나타내준다.


그리고 처음에 뽑은 구역들이 선거구를 이룰 수 있는지(모두 연결되어 있는지) 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
121
122
123
124
125
126
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
 
int n, pop[11], tot = 0, Min = 987654321, st = 1;
bool vis[11], map[11][11], used[11];
queue<int> q;
 
int bfs(int st, bool usedCheck) { //true인 경우가 처음 뽑은 구역들 연결 확인하는 경우
    q.push(st);
    vis[st] = true;
    int restSum = pop[st];
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (usedCheck)
                if (!used[i]) continue; //뽑은 곳들에 대해서만 연결 관계 확인
            
            if (!map[cur][i] || vis[i]) continue;
            
            q.push(i);
            vis[i] = true;
            restSum += pop[i];
        }
    }
    return restSum; //선거구 인원 반환
}
 
void process() {
    int pickedSum, restSum;
    
 
    //처음에 뽑은 게 모두 연결되어 있는지 확인
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            pickedSum = bfs(i, true);
            break;
        }
    }
 
    bool firCon = true;
    for (int i = 1; i <= n; i++) {
        if (used[i]) { //뽑은 것중에
            if (!vis[i]) firCon = false; //연결 안 된거 하나라도 있으면 거르기
        }
    }
 
    for (int i = 1; i <= n; i++) //방문 처리 배열 초기화
        vis[i] = false;
 
    if (!firCon) return;
 
 
    for (int i = 1; i <= n; i++) 
        if (used[i]) vis[i] = true; //확정된 선거구 방문처리
    
    for(int i = 1; i <= n; i++) {
        if (!vis[i]) {
            restSum = bfs(i, false); //나머지 선거구 인원 계산 + 연결 관계 확인
            break;
        }
    }
 
    bool allCon = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { //선거구 형셩 불가
            allCon = false;
            break;
        }
    }
    
    if(allCon) {
        int dif = abs(tot - restSum - restSum);
        if (Min > dif) Min = dif;
    }
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}
void btk(int cnt) {
    if (cnt >= 1) {
        if (cnt >= 6) return;
        //전부 다 뽑은 경우 제외
        process();
    }
    
    if (cnt == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            btk(cnt + 1);
            used[i] = false;
        }
    }
}
 
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pop[i];
        tot += pop[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int edgeCnt;
        cin >> edgeCnt;
        while (edgeCnt--) {
            int dst;
            cin >> dst;
            map[dst][i] = true;
            map[i][dst] = true;
        }
    }
 
    btk(0);
 
    if (Min == 987654321) cout << -1;
    else
        cout << Min;
 
    return 0;
}
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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



초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.




사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.



그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.



사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.



사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,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
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
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
int col, m, row, map[31][11], st = 0;
bool isused[31][11], ansUpdate = false;
vector<pii> v;
int ans = -1;
 
void btk(int k, int num) {
    if (k == num) { //사다리의 개수
        
        bool suc = true; //답을 찾았는지
        for (int i = 1; i <= col; i++) {
            pii pos = { 1, i }; //출발 지점
            bool isFirst = true; //true면 가로로 이동, false면 세로로 이동
            while (pos.first <= row) {
                
                if (map[pos.first][pos.second] != 0) { //가로 사다리 만나면
                    if (isFirst == true) { //가로이동 할 차례
                        pos.second = map[pos.first][pos.second];
                        isFirst = false; //다음엔 세로 이동 하도록
                        
                    }
                    else { //세로로 이동할 차례
                        isFirst = true; //다음엔 가로로 이동하도록
                        pos.first++;
                        
                    }
                }
                else 
                    pos.first++; //가로 사다리가 없는 곳이면 아래로 이동
                
            }
            if (pos.second != i) { //출발점과 도착지점의 열값이 다르면 실패
                suc = false;
                break;
            }
        }
        if (suc) {
            ansUpdate = true;
            ans = num;
        }
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        int r = v[i].first; //r,c와 r,c+1이 사다리
        int c = v[i].second;
        if (!isused[r][c] && !isused[r][c + 1]) {
            isused[r][c] = true;
            isused[r][c + 1] = true;
            st = i;
            map[r][c] = c + 1; //r,c에서 사다리를 보면 r, c+1로 이동
            map[r][c + 1] = c; //위와 반대
            btk(k + 1, num);
            if (ansUpdate) return; //정답 찾으면 백트레킹 그만
            isused[r][c] = false;
            isused[r][c + 1] = false;
            map[r][c] = 0;
            map[r][c + 1] = 0;
        }
    }
}
int main(void) {
    cin >> col >> m >> row;
    for (int i = 0; i < m; i++) {
        int rw, st;
        cin >> rw >> st;
        map[rw][st] = st + 1;
        map[rw][st + 1] = st;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) 
            if (map[i][j] != 0)
                isused[i][j] = true; //처음부터 가로 사다리가 놓여진 곳
    
 
    //가로막대 놓을 수 있는 곳 찾아서 벡터에 시작점만 담기
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col - 1; j++) { //어짜피 가장 끝 열에는 사다리를 둘 수 없으니까 col -1
            if (!isused[i][j] && !isused[i][j + 1]) {
                isused[i][j] = true;
                isused[i][j + 1] = true;
                v.push_back({ i, j });
                isused[i][j] = false;
                isused[i][j + 1] = false;
            }
        }
    }
    
    
    for (int i = 0; i <= 3; i++) {
        if (ansUpdate) break; //최솟값 찾는 거니까 하나라도 찾으면 그만
        btk(0, i);
    }
    printf("%d", ans);
    return 0;
}
cs


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

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

백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20

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



궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.



따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.


각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.


이때 중요한 것이 몇가지 있다.


궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.


또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.


그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.


set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.



세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.



시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.


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
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef pair<int, int> pii;
int m[19][18], tmp[19][18], N, M, d, st = 1, arr[19], dis[19][18];
int dr[3] = { 0,-1,0 }, dc[3] = {-1, 0, 1};
bool isused[18];
queue<pii> q;
set<pii> killed;
 
void bfs(pii start) {
    dis[start.first][start.second]++;
    q.push(start);
    while (!q.empty()) {
        pii cur = q.front(); q.pop();
        if (dis[cur.first][cur.second] >= d) continue; //사정거리 마지막 점
        for (int i = 0; i < 3; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] >= 0) continue;
            if (m[nr][nc] == 1) {
                killed.insert({ nr, nc });
                return;
            }
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
}
void init() {
    for(int i = 1 ; i <= N+1 ; i++)
        for(int j = 1 ; j <= M ; j++)
            dis[i][j] = -1;
    while (!q.empty()) q.pop();
}
bool allKilled() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) 
            if (m[i][j] != 0) 
                return false;
        
    return true;
}
int kill() {
    int cnt = 0;
    for (set<pii>::iterator itr = killed.begin(); itr != killed.end(); itr++) {
        m[itr->first][itr->second] = 0;
        cnt++;
    }
    killed.clear();
    return cnt;
}
void move() {
    for (int i = N; i >= 1; i--) 
        for (int j = 1; j <= M; j++) 
            m[i][j] = m[i - 1][j];
}
int ans = 0;
void btk(int k) {
    if (k == 3) {
        
        int killSum = 0;
        while (1) {
            //적 다 사라질 때까지
            if (allKilled()) break;
 
            for (int i = 0; i < 3; i++) {
                bfs({ N + 1, arr[i] });
                init();
            }
            killSum += kill();//죽은 적들 배열에서 제거
        
            move();    
        }
        if (ans < killSum) ans = killSum;
        
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                m[i][j] = tmp[i][j];
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i <= M; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            btk(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> N >> M >> d;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    btk(0);
    cout << ans;
    return 0;
}
cs


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

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

백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19

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



오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.



우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.


따라서 자리번호를 매겼다.


그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 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
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
#include<iostream>
#include<string>
#include<queue>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int seat[6][6];
bool isused[25];
int st = 0, arr[8], dis[6][6], map[6][6];
queue<pair<int, int> > q;
int res = 0;
bool endFlag = false;
 
void process() {
    int idx = 0;
    endFlag = false;
    for (int i = 0; i < 5; i++) { //뽑힌 학생의 자리번호 1로
        for (int j = 0; j < 5; j++) {
            if (seat[i][j] == arr[idx]) {
                map[i][j] = 1;
                idx++;
                //if (idx == 7) return; 이 구문 때문에 아래 카운트가 안먹혀서 시간낭비
            }
        }
    }
 
    int sCnt = 0;
    //소영 카운트
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) 
            if (map[i][j] == 1 && m[i][j] == 'S') sCnt++;
        
    
    if (sCnt < 4) endFlag = true;
}
void init() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            map[i][j] = 0; //자리번호 배열 초기화
            dis[i][j] = -1; //방문처리 배열
        }
    
}
 
void bfs(pair<int, int> start) {
    q.push(start);
    dis[start.first][start.second]++;
    int cnt = 0;
    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 >= 5 || nc >= 5) continue;
            if (dis[nr][nc] >= 0 || map[nr][nc] != 1) continue;
            q.push({ nr, nc });
            cnt++;
            dis[nr][nc] = cnt;
        }
    }
    
    if (cnt == 6) //7명이 붙어 앉은 경우
        res++;
    
}
 
void pick(int k) {
    if (k == 7) { //1. 자리번호 7개 선택
    
        init(); 
 
        process();
        if (endFlag) return;
 
        for (int i = 0; i < 5; i++) 
            for (int j = 0; j < 5; j++) 
                if (map[i][j] == 1 && dis[i][j] < 0) 
                    bfs({ i, j }); 
        
        return;
    }
    
    if (k == 0) st = 0;
    for (int i = st; i < 25; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            pick(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int cnt = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            cin >> m[i][j];
            seat[i][j] = cnt;
            cnt++;
        }
    
    pick(0);
    cout << res;
    return 0;
}
 
cs


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

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

백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09

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


순열과 조합을 적절히 사용해주면 되는 문제였다.


먼저 팀을 나누기 위해서는 순서는 중요하지 않기 때문에 조합으로 뽑는다.


0, 1, 2, 3, 4, 5 이렇게 6명의 사람이 있으면 조합으로 3개를 뽑아서 두 개의 팀을 만들어 준다.


이어서 팀 각각에 대해서 보자.


예를 들어 스타트 팀이 0, 1, 2로 결정되면 링크 팀은 자연스럽게 3, 4, 5로 결정된다.


이제 팀 각각에 대해서 점수를 계산해주면 된다.


S01과 S10이 다르다고 했다. 따라서 스타트팀의 경우에 대해서 순열로 뽑아준다. 총 3P2가지가 나올 것이다.


이를 더해서 점수 하나를 만들어주고, 링크팀에 대해서도 진행해준다. 이제 점수차이의 최솟값을 찾으면 된다.



점수 계산시 순열을 사용하지 않고, 조합으로 뽑은 이후에, 순서를 뒤집어서 계산을 추가해줘도 동일한 결과가 나온다. 하지만 순열로 처리하면 한 번에 처리할 수 있기 때문에 순열을 사용했다.



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
#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n, m[21][21], st = 0, arr[11], sco[11]; //arr이 팀1, sco가 자리순열
vector<int> v; //팀2
 
bool isused[21], isused2[11];
int Sum = 0, Sum2 = 0, res = 200;
void cntScore(int k, int a[]) { //스타트팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
    
        Sum += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = a[i];
            isused2[i] = true;
            cntScore(k + 1, a);
            isused2[i] = false;
        }
    }
}
void cntScore2(int k) { // 링크팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
        
        Sum2 += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = v[i];
            isused2[i] = true;
            cntScore2(k + 1);
            isused2[i] = false;
        }
    }
}
void makeTeam(int k) { //팀 선택은 조합으로 한다.
    if (k == n / 2) {
 
        for (int i = 0; i < n; i++) //팀1에서 선택 안 된 애들이 팀2로
            if (!isused[i]) v.push_back(i);
        
        cntScore(0, arr); //팀1 점수 계산
        
        cntScore2(0); //팀2 점수 계산
        
        res = min(res, abs(Sum - Sum2));
        Sum = 0, Sum2 = 0;
        v.clear();
 
        return;
    }
 
    if (k == 0) st = 0;
    for (int i = st; i < n; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            makeTeam(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    makeTeam(0);
    cout << res;
    return 0;
}
cs



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

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

백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 15683번: 감시 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07

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



문제를 보면, 카메라의 전체 개수가 8개로 많지 않다. 카메라의 종류별로 가능한 각도들을 모두 시뮬레이션해주면 되겠다.


각각의 카메라가 가질 수 있는 상태를 번호로 지정했다. 1번 카메라는 0~3번 상태, 2번 카메라는 4번~5번 상태... 이런 방식이다.


이제 카메라들이 띄고 있을 수 있는 상태를 조합으로 뽑아주면 된다.



이때 1번 카메라는 0~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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include<iostream>
#include<vector>
 
using namespace std;
 
int R, C, map[10][10], tmp[10][10];
struct CAMPOS {
    int idx; //카메라 번호
    int r;
    int c;
};
vector<CAMPOS> cv;
bool isused[10][4]; //카메라 8개, 각도 사용 정보
bool masterUsage[9];
int cam[10][4]; //i번째 순서 카메라가 가질 수 있는 각도 저장
int arr[10], st = 0, st2 = 0, res = 100;
void init() {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 4; j++)
            cam[i][j] = -1;
}
 
void process() {
    //arr에 카메라 각도 번호
    for (int i = 0; i < cv.size(); i++) {
        int cr = cv[i].r;
        int cc = cv[i].c;
        if (arr[i] == 0) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 1) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 2) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 3) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 4) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 5) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 6) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 7) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 8) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 9) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 10) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 11) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 12) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 13) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 14) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
    }
}
void backTracking(int k) {
    if (k == cv.size()) {
 
        process();
 
        //사각지대 계산
        int cnt = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] == 0) cnt++;
 
        if (res > cnt) 
            res = cnt;
 
        //원상복구
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                map[i][j] = tmp[i][j];
        return;
    }
 
    if (k == 0) st = 0;
 
    for (int i = st; i < cv.size(); i++) {
        if (!masterUsage[i]) {
            masterUsage[i] = true;
            //i번카메라가 사용중이 아니면서
            //if (k == 0) st2 = 0;
            for (int j = 0; j < 4; j++) {
                if (cam[i][j] != -1 && !isused[i][j]) {
                    //존재하는 카메라 각도이면서 사용중이 아닌 각도라면
                    arr[k] = cam[i][j];
                    isused[i][j] = true;
                    st = i;
                    //st2 = j;
                    backTracking(k + 1);
                    isused[i][j] = false;
                }
            }
            masterUsage[i] = false;
        }
 
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            tmp[i][j] = map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6) {
                CAMPOS tmp;
                tmp.r = i;
                tmp.c = j;
                tmp.idx = map[i][j];
                cv.push_back(tmp); //cv에 카메라 정보 저장
            }
        }
 
    init();
 
    for (int i = 0; i < cv.size(); i++) {
        if (cv[i].idx == 1) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j;
        }
        else if (cv[i].idx == 2) {
            for (int j = 0; j < 2; j++)
                cam[i][j] = j + 4;
        }
        else if (cv[i].idx == 3) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 6;
        }
        else if (cv[i].idx == 4) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 10;
        }
        else if (cv[i].idx == 5) {
            cam[i][0] = 14;
        }
    }
 
    backTracking(0);
    cout << res << '\n';
 
}
cs


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

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

백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07
백준 14502번: 연구소 (C++)  (0) 2019.08.07
백준 15685번: 드래곤 커브 (C++)  (0) 2019.08.06
백준 15686번: 치킨 배달 (C++)  (0) 2019.08.05

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/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

+ Recent posts

티스토리툴바