https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=1233&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 트리 정보를 입력받는다.

2. 해당 트리 연산식의 유효성을 출력한다.

 

<해법>
1. 트리 연산식의 유효성을 판단하는 방법

=> 계산되는 방법을 살펴보면, 연산자 노드는 자식이 있어야하고 숫자 노드는 자식이 없어야합니다. 또한 연산자 노드는 자식이 꼭 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
#include <iostream>
 
using namespace std;
 
int N;
bool answer;
 
bool isOper(char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/') return true;
    return false;
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        answer = true;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            char data;
            cin >> idx >> data;
 
            int cnt = 0;
            if (isOper(data)) cnt = 2;
            int childCnt = 0;
            while (getc(stdin) == ' ') {
                int trash;
                cin >> trash;
                childCnt++;
            }
            if (childCnt != cnt) answer = false;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

자료구조 트리에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 5656 - 벽돌 깨기(2)  (0) 2023.01.02
[C++] SWEA 1232 - 사칙연산  (1) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE&problemTitle=1231&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 트리 정보를 입력받는다.

2. 트리를 중위순회해서 얻은 문자열을 출력한다.

 

<해법>

1. 트리 정보 저장 방법

=> 문제에서 트리는 완전 이진탐색으로 주어집니다. 따라서, 배열로 구현할 수 있고 각 노드의 자식들은 (본인 index * 2), (본인 index * 2 + 1)로 나타낼 수 있습니다.(루트노드를 index 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
#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
char tree[101];
string answer;
 
string inOrderSearch(int idx) {
    if (idx > N) return "";
 
    string ret = "";
    ret = inOrderSearch(idx * 2) + tree[idx] + inOrderSearch((idx * 2) + 1);
    return ret;
}
 
void solution() {
    answer = inOrderSearch(1);
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        memset(tree, NULL, sizeof(tree));
        answer = "";
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            char c;
            cin >> idx >> c;
            tree[idx] = c;
 
            int trash;
            while (getc(stdin) == ' ') {
                cin >> trash;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

중위순회에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1232 - 사칙연산  (1) 2022.12.31
[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14zIwqAHwCFAYD 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 암호문과 명령어를 입력받는다.

2. 암호문을 명령어에 맞게 수정하고, 암호문의 처음 10개의 숫자를 출력한다.

 

<해법>

1. 자료구조 선택하기

=> 저는 list 자료구조를 선택하였습니다. I 명령어는 list의 splice를, D는 erase를, A는 push_back를 사용하여 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <list>
 
using namespace std;
 
int N;
list<int> code;
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        code.clear();
 
        //입력 및 해법
        cin >> N;
        for (int i = 0; i < N; i++) {
            int num = 0;
            cin >> num;
            code.push_back(num);
        }
        cin >> N;
        for (int i = 0; i < N; i++) {
            char cmd;
            int x, y, s;
            cin >> cmd;
            if (cmd == 'I') {
                cin >> x >> y;
                list<int> add;
                for (int j = 0; j < y; j++) {
                    cin >> s;
                    add.push_back(s);
                }
                auto iter = code.begin();
                while (x--) iter++;
                code.splice(iter, add);
            }
            else if (cmd == 'D') {
                cin >> x >> y;
                auto iter = code.begin();
                while (x--) iter++;
                while (y--) {
                    iter = code.erase(iter);
                }
            }
            else {
                cin >> y;
                for (int j = 0; j < y; j++) {
                    cin >> s;
                    code.push_back(s);
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " ";
        for (int i = 0; i < 10; i++) {
            cout << code.front() << " ";
            code.pop_front();
        }
        cout << "\n";
    }
 
    //종료
    return 0;
}

 

리스트 자료구조에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=5644&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 배터리 BC 정보와 사용자 이동 정보를 입력받는다.

2. 사용자가 충전한 양의 합의 최댓값을 출력한다.

 

<해법>

1. 사용자가 충전한 양의 합이 최대가 되는 BC 선택하기

=> 사용자 한명씩 모두 BC를 선택해보아야 합니다. 따라서, 저는 재귀함수를 이용해서 브루트포스를 구현하였습니다.

 

2. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 주어진 사용자 이동 정보를 이용해 시뮬레이션을 진행한다.

(2) 사용자가 이동할 때마다, 재귀함수를 이용해 충전한 양의 최댓값을 구한다.

(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
#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
struct bc {
    pos p;
    int c;
    int power;
};
 
int dx[] = { 0,-1,0,1,0 };
int dy[] = { 0,0,1,0,-1 };
 
int M, A;
int dir[2][101];
bc BC[8];
pos user[2];
bool visited[8];
int answer;
 
bool canCharge(pos p, int num) {
    if (abs(p.x - BC[num].p.x) + abs(p.y - BC[num].p.y) <= BC[num].c) return true;
    return false;
}
 
int chargeAmount(int idx) {
    if (idx == 2) return 0;
 
    int ret = 0;
    for (int i = 0; i < A; i++) {
        if (canCharge(user[idx], i) && !visited[i]) {
            visited[i] = true;
            ret = max(ret, chargeAmount(idx + 1) + BC[i].power);
            visited[i] = false;
        }
    }
    ret = max(ret, chargeAmount(idx + 1));
    return ret;
}
 
int simulation() {
    int output = 0;
    user[0].x = 1, user[0].y = 1, user[1].x = 10, user[1].y = 10;
    
    for (int time = 0; time <= M; time++) {
        for (int i = 0; i < 2; i++) {
            user[i].x += dx[dir[i][time]];
            user[i].y += dy[dir[i][time]];
        }
        output += chargeAmount(0);
    }
   
    return output;
}
 
void solution() {
    answer = simulation();
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        M = 0, A = 0;
        memset(dir, 0, sizeof(dir));
        for (int i = 0; i < 8; i++) {
            BC[i] = { 0,0,0,0 };
        }
        for (int i = 0; i < 2; i++) {
            user[i] = { 0,0 };
        }
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> M >> A;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= M; j++) {
                cin >> dir[i][j];
            }
        }
        for (int i = 0; i < A; i++) {
            int x = 0, y = 0, c = 0, power = 0;
            cin >> y >> x >> c >> power;
            BC[i] = { {x,y},c,power };
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

시뮬레이션과 DFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24
[C++] SWEA 5650 - 핀볼 게임(2)  (0) 2022.12.23

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14wL9KAGkCFAYD&categoryId=AV14wL9KAGkCFAYD&categoryType=CODE&problemTitle=1227&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 미로를 입력받는다.

2. 미로 출발점부터 도착점까지 갈 수 있는지 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 길찾기 알고리즘으로 DFS(스택, 재귀함수), BFS(큐)가 있습니다. 모든 방법으로 풀이가 가능합니다(모든 방법으로 풀어보았습니다). 저는 미로 1에서 DFS(재귀함수)를 이용한 코드를 올렸으므로, 이번에는 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
#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int trash;
char map[100][100];
pos start;
bool answer;
 
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= 100 || p.y >= 100) return false;
    return true;
}
 
bool findRoute() {
    queue<pos> q;
    bool visited[100][100];
    memset(visited, false, sizeof(visited));
 
    q.push(start);
    visited[start.x][start.y] = true;
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
        if (map[cur.x][cur.y] == '3') return true;
        for (int i = 0; i < 4; i++) {
            pos nxt = cur;
            nxt.x += dx[i];
            nxt.y += dy[i];
            if (isInner(nxt) && map[nxt.x][nxt.y] != '1' && !visited[nxt.x][nxt.y]) {
                q.push(nxt);
                visited[nxt.x][nxt.y] = true;
            }
        }
    }
    return false;
}
 
void solution() {
    answer = findRoute();
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        trash = 0;
        memset(map, '0', sizeof(map));
        start = { 0,0 };
        answer = false;
 
        //입력
        cin >> trash;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                cin >> map[i][j];
                if (map[i][j] == '2') {
                    start = { i,j };
                }
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

BFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24
[C++] SWEA 5650 - 핀볼 게임(2)  (0) 2022.12.23
[C++] SWEA 1226 - 미로1  (0) 2022.12.21

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD&categoryId=AV14uWl6AF0CFAYD&categoryType=CODE&problemTitle=1225&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 8개의 숫자를 입력받는다.

2. 주어진 작업을 종료된 후 8개의 숫자를 출력한다.

 

<해법>

1. 하나하나씩 다 해봐야 할까?

=> 사실 이 문제를 푸는 것은 간단합니다. 큐를 이용해서 주어진 조건에 맞게 구현하는 것은 어렵지 않은 일입니다. 하지만, 테스트케이스처럼 큰 숫자가 나올경우 너무 오래걸릴거란 생각이 듭니다. 꼭 하나하나씩 1,2,3,4,5,1,2,3,4,5... 순서로 빼봐야할까요? 아닙니다. 잘 생각해보면, 8사이클이 돌 경우 모든 숫자에서 1+2+3+4+5 = 15의 숫자가 빠지게 됩니다. 따라서, 모든 숫자에서 15씩 동일하게 여러번 뺄 수 있습니다. 그렇지만, 여기서 조금 더 생각해서 숫자가 15,30,45 등등 15의 배수일 경우를 생각해야합니다. 이 때는 0이 될때까지 빼면 안됩니다. 왜냐하면 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
#include <iostream>
#include <string.h>
#include <queue>
#define INF 987654321
 
using namespace std;
 
int trash;
int arr[8];
queue<int> q;
int minimum;
 
void solution() {
    int div = minimum / 15;
    int remainder = minimum % 15;
    div = (remainder == 0) ? div - 1 : div;
    for (int i = 0; i < 8; i++) {
        arr[i] -= (15 * div);
    }
    for (int i = 0; i < 8; i++) {
        q.push(arr[i]);
    }
    while (true) {
        for (int i = 1; i <= 5; i++) {
            int tmp = q.front() - i;
            q.pop();
            q.push((tmp <= 0 ? 0 : tmp));
            if (tmp <= 0) return;
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        trash = 0;
        memset(arr, 0, sizeof(arr));
        while (!q.empty()) q.pop();
        minimum = INF;
 
        //입력
        cin >> trash;
        for (int i = 0; i < 8; i++) {
            int num;
            cin >> num;
            arr[i] = num;
            minimum = min(minimum, num);
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " ";
        while (!q.empty()) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << "\n";
    }
 
    //종료
    return 0;
}

 

수학적인 사고와 구현에 대해 알아볼 수 있었습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 5650 - 핀볼 게임(2)  (0) 2022.12.23
[C++] SWEA 1226 - 미로1  (0) 2022.12.21
[C++] SWEA 1224 - 계산기3  (0) 2022.12.21

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 게임판을 입력받는다.

2. 핀볼을 굴려서 얻을 수 있는 점수의 최댓값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 게임판의 0인 곳에서 4방향으로 핀볼을 모두 굴려봐야합니다. 따라서, 저는 브루트포스를 선택했습니다.

 

2. 시뮬레이션 구현하기

=> 조건에 맞게 정확하게 구현하기만 하면 되는 시뮬레이션입니다. 구현에 정답은 없지만, 저가 좀 더 쉽게 구현하기 위해 만들었던 장치들을 소개하겠습니다.

(1) 게임판을 102x102로 만든다.

게임판을 102x102로 만들면, 벽을 처리하는 구현이 간단해집니다. 왜냐하면 벽도 하나의 공간으로 생각할 수 있기 때문입니다. 

(2) 게임판 테두리를 5번 블록으로 채운다.

결국 게임판 외곽의 벽들은 핀볼의 방향을 반대방향으로 바꾸는 5번 블록과 성질이 같습니다. 게임판 외곽을 5번 블록으로 채우면 벽도 블록으로 생각할 수 있으므로 구현이 간단해집니다.

(3) 만나는 블록과 핀볼의 방향에 따라 바뀌는 핀볼 방향을 미리 2차원 배열로 구현한다.

미리 만들어 놓으면, 핀볼이 바뀌는 방향을 쉽게 구할 수 있습니다.

 

3. 최적화할 수 있을까?

=> 조금 더 깊게 생각해보겠습니다. 핀볼의 방향이 반대로 바뀌면, 다시 왔던 길을 그대로 돌아서 갑니다. 이 말은 곧 무조건 시작지점으로 돌아가게 되어있고, 부딪혔던 벽도 다시 부딪히게 된다는 뜻입니다. 따라서 핀볼의 방향이 반대로 될 때, 점수는 (지금까지 점수 x 2 + 1)이되고 시뮬레이션을 종료할 수 있습니다. 위 방법으로 연산 횟수를 조금이나마 줄일 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int block[6][4] = { //-1은 왔던 방향의 반대로 가는 경우
    {0,0,0,0},
    {-1,-1,1,0},
    {1,-1,-1,2},
    {3,2,-1,-1},
    {-1,0,3,-1},
    {-1,-1,-1,-1}
};
 
int N;
int map[102][102];
vector<pos> wormhole[11];
int answer;
 
bool isStart(pos p, pos start) {
    if (p.x == start.x && p.y == start.y) return true;
    return false;
}
 
bool isBlackhole(pos p) {
    if (map[p.x][p.y] == -1) return true;
    return false;
}
 
bool isBlock(pos p) {
    if (1 <= map[p.x][p.y] && map[p.x][p.y] <= 5) return true;
    return false;
}
 
bool isEmptySpace(pos p) {
    if (map[p.x][p.y] == 0) return true;
    return false;
}
 
bool isWormhole(pos p) {
    if (6 <= map[p.x][p.y] && map[p.x][p.y] <= 10) return true;
    return false;
}
 
pos getPairWormhole(int num, pos p) {
    if (wormhole[num][0].x == p.x && wormhole[num][0].y == p.y) return wormhole[num][1];
    else return wormhole[num][0];
}
 
int simulation(pos start, int startDir) {
    int score = 0;
    pos p = start; 
    int dir = startDir;
    while (true) {
        p.x += dx[dir], p.y += dy[dir];
        //시작지점 or 블랙홀
        if (isStart(p, start) || isBlackhole(p)) break;
        //블록
        else if (isBlock(p)) {
            int blockNum = map[p.x][p.y];
            dir = block[blockNum][dir];
            if (dir == -1) {
                score = (score * 2) + 1;
                break;
            }
            else score++;
        }
        //웜홀
        else if (isWormhole(p)) {
            p = getPairWormhole(map[p.x][p.y], p);
        }
    }
    return score;
}
 
void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isEmptySpace({ i,j })) {
                for (int k = 0; k < 4; k++) {
                    answer = max(answer, simulation({ i, j }, k));
                }
            }
        }
    }
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        memset(map, 0, sizeof(map));
        for (int i = 6; i <= 10; i++) wormhole[i].clear();
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 1; i <= N; i++) {
            map[i][0] = 5, map[i][N + 1] = 5, map[0][i] = 5, map[N + 1][i] = 5;
            for (int j = 1; j <= N; j++) {
                cin >> map[i][j];
                if (isWormhole({ i,j })) wormhole[map[i][j]].push_back({ i,j });
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24
[C++] SWEA 1226 - 미로1  (0) 2022.12.21
[C++] SWEA 1224 - 계산기3  (0) 2022.12.21
[C++] SWEA 1219 - 길찾기(2)  (0) 2022.12.21

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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

<풀이>

1. 구역의 정보를 입력받는다.

2. 조건에 맞게 구역들을 두 개의 선거구에 포함시키고, 두 선거구간 인구 차이의 최솟값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우를 다 해보아야합니다. 따라서, 저는 브루트포스를 선택하였습니다. 하지만, 여기서 한번 멈칫했습니다. 구역들은 한 선거구가 되려면 모두 연결되어있어야합니다. 그러면 이 조건을 (1)구역들을 뽑을 때 검사해야하나 (2)구역을 다 나눠놓고 검사해도되나 망설여집니다. 저는 시간복잡도를 따져보았습니다. 구역은 10개 이하로 주어지므로, 연산횟수는 1024회 입니다. 따라서, 저는 (2)를 선택했습니다.

 

2. 구역들이 모두 연결되어있는지 확인하기

=> 구역들을 두 개로 나누었다면, 같은 선거구의 구역들이 모두 연결되어있는지 확인해야 합니다. 저는 BFS를 이용해서 조건을 확인했습니다.

 

3. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다. 구역들을 두 선거구로 나누는 모든 경우를 해본다.

(2) 두 선거구로 나누었으면, ①두 선거구에 구역들이 하나라도 포함되어있는지 확인하고, ②같은 선거구에 있는 구역들이 모두 연결되어있는지 확인합니다. 

(3) 두 선거구간 인구차이의 최소를 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
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#define INF 987654321
 
using namespace std;
 
int N;
int people[11];
bool edge[11][11];
vector<int> a, b;
int answer;
 
bool isLinked(vector<int> sector) {
    queue<int> q;
    bool visited[11];
    memset(visited, false, sizeof(visited));
 
    int start = sector.front();
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < sector.size(); i++) {
            int nxt = sector[i];
            if (!visited[nxt] && edge[cur][nxt]) {
                q.push(nxt);
                visited[nxt] = true;
            }
        }
    }
 
    for (int i = 0; i < sector.size(); i++) {
        int node = sector[i];
        if (!visited[node]) return false;
    }
    return true;
}
 
int divideSector(int idx, int sumA, int sumB) {
    if (idx > N) {
        if (!sumA || !sumB) return INF;
        else {
            if (isLinked(a) && isLinked(b)) return abs(sumA - sumB);
            else return INF;
        }
    }
 
    int ret = INF;
    //a구역에 넣는 경우
    a.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA + people[idx], sumB));
    a.pop_back();
    //b구역에 넣는 경우
    b.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA, sumB + people[idx]));
    b.pop_back();
    return ret;
}
 
void solution() {
    answer = divideSector(1, 0, 0);
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 0;
    memset(people, 0, sizeof(people));
    memset(edge, false, sizeof(edge));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> people[i];
    }
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int node = 0;
            cin >> node;
            edge[i][node] = true;
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 BFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17406 - 배열 돌리기 4  (1) 2022.12.22
[C++] 백준 17281 - 야구(⚾)  (0) 2022.12.22
[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21

+ Recent posts

티스토리툴바