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

 

17837번: 새로운 게임 2

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽

www.acmicpc.net

시뮬레이션 문제이다. 어떻게 말의 정보들을 저장하고 말을 이동시킬까 고민하다가 다음과 같이 구현해봤다.

 

 

 

말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.

벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.

 

방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.

 

말을 이동시키기 위해서는 deque배열을 사용하였다.

deque<int> dq[13][13];

위와같이 deque<int>를 타입으로 가지는 2차원 배열이다.

dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.

 

(queue가 아닌 deque를 사용한 이유는 이동할 칸이 빨간색인경우 순서를 반대로 넣어주기 위해서 사용하였다.)

(효율적인 방법인지는 잘모르겠다. 채점현황을 보니 메모리를 더 사용하는 것 같은데 다른 분들 풀이도 찾아봐야겠다...)

 

 

 

이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.

문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.

각 턴에서는 1번말부터 k번말까지 순차적으로 이동시킨다.

 

 

 

이동할 칸이

  1. 범위를 벗어나거나 파란색 칸인 경우
    • 원래 좌표에서 방향을 반대로 바꾼다.
      1. 다시 한칸을 이동할건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼채로 더 이동하지 않는다.
      2. 그렇지 않다면 이동을 한건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
  2.  흰색인 경우
    • 현재 이동할 말의 번호가 num이라고 했을때
    • 현재 이동할 말의 위에 있는 말들을 함께 이동시켜주기위해서 deque에서 num번 말이 나오는 이후의 말들은 모두 같이 이동시켜주면된다.
    • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서
      1. num번이 나오지 않았다면 다시 원래 위치 deque에 넣어준다.
      2. num번이 나왔거나 이전에 num번이 나왔다면 이동할 위치의 deque에 넣어준다. (이동할 때는 해당 말의 위치정보(벡터에 넣어놓은 값)을 업데이트 해주어야한다)
  3. 빨간색인 경우
    • 현재 이동할 말의 번호가 num이라고 했을때
    • 현재 이동할 말의 위에 있는 말들을 순서를 반대로 이동시켜주기 위해서 deque의 뒷부분부터 num번까지의 말들을 순차적으로 이동시켜준다.
    • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서 num이 나올때까지 이동할 위치의 deque에 넣어주고 num번이 나온다면 num번말도 이동시켜주고 반복문을 종료한다.

 

 

 

이동을 매번 할때마다 이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고

4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.

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
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
 
int n, k;
int map[13][13];
 
//오, 왼, 위, 아래
int dx[] = { 0,0,0,-1,1 };
int dy[] = { 0,1,-1,0,0 };
 
 
deque<int> dq[13][13];
 
struct Horse {
    int x;
    int y;
    int dir;
    Horse(int a, int b, int c) {
        x = a;
        y = b;
        dir = c;
    }
};
 
 
//말의 정보를 저장할 벡터
vector<Horse> vt;
 
 
bool move(int num) {
 
    //num번호 말의 좌표와 방향
    int x = vt[num].x;
    int y = vt[num].y;
    int dir = vt[num].dir;
 
    int nx, ny, tmp;
    
    //이동할 좌표
    nx = x + dx[dir];
    ny = y + dy[dir];
 
 
    //이동할 좌표가 파란색이거나 범위를 벗어나는 경우
    if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
        //방향 전환
        if (dir == 1 || dir == 3) dir++;
        else dir--;
 
        //반대로 다시 한칸 이동
        nx = x + dx[dir];
        ny = y + dy[dir];
        
 
        //말의 방향정보 업데이트
        vt[num].dir = dir;
 
 
        //다시 이동한 칸이 또 파란색이거나 범위를 벗어나면 방향만 바꾸고 리턴
        if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
            return false;
        }
 
        //그렇지 않다면 아래남은 코드 진행
    }
    
 
    //이동할 칸이 흰색인 경우
    if (map[nx][ny] == 0) {
        bool flag = false;
 
        int size = dq[x][y].size();
        for (int i = 0; i < size; i++) {
            tmp = dq[x][y].front();
            dq[x][y].pop_front();
 
            if (tmp == num || flag) {
                //num번 말이랑 num위에 있는 말들만 이동한다.
                flag = true; //ture로 바꿔주면 앞으로 뒤에 있는 말들은 같이 이동한다.
 
 
                //이동시켜준다.
                dq[nx][ny].push_back(tmp);
                
                //좌표정보 업데이트
                vt[tmp].x = nx;
                vt[tmp].y = ny;
            }
            else {
                //num번 말 아래있는 말은 다시 원래좌표에 넣어준다.
                dq[x][y].push_back(tmp);
            }
        }
 
    }
    else if (map[nx][ny] == 1) {
    //이동할 칸이 빨간색인 경우
 
        int size = dq[x][y].size();
        for (int i = 0; i < size; i++) {
            //반대 순서로 넣어줄 것이므로 뒤에것을 빼준다.
            tmp = dq[x][y].back();
            dq[x][y].pop_back();
 
 
            //이동시켜준다.
            dq[nx][ny].push_back(tmp);
 
            //좌표정보 업데이트
            vt[tmp].x = nx;
            vt[tmp].y = ny;
 
            //num번말 위에있는말들과 num번말까지만 이동시키므로 break
            if (tmp == num) break;
        }
    }
 
 
    //말이 4개 이상 쌓이면 true를 리턴
    if (dq[nx][ny].size() >= 4) return true;
    else return false;
}
 
 
 
int turnStart() {
    int turnCnt = 1;
 
 
    while (turnCnt <= 1000) {
        
        bool flag = false;
 
        for (int i = 1; i <= k; i++) {
            flag = move(i);
 
            //말이 4개이상 쌓여서 true값을 리턴받았다면 게임 종료(턴 수를 리턴)
            if (flag) return turnCnt;
        }
        
        turnCnt++;
    }
 
 
    //1000번이 넘으면 -1을 리턴
    return -1;
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //1번부터 사용하기 위해 0번째 위치에는 쓰레기값 넣어 놓는다.
    vt.push_back(Horse(-1, -1, -1));
 
 
    int x, y, d;
    for (int i = 1; i <= k; i++) {
        cin >> x >> y >> d;
 
        //말의 정보를 벡터에 넣는다.
        vt.push_back(Horse(x, y, d));
 
        //말이 있는 좌표에 말의 번호를 넣는다.
        dq[x][y].push_back(i);
    }
 
 
    cout <<  turnStart() << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1938. 통나무 옮기기  (0) 2020.02.12
[BOJ] 17780. 새로운 게임  (0) 2020.02.03
[BOJ] 1600. 말이 되고픈 원숭이  (0) 2020.02.01
[BOJ] 2532. 반도체 설계  (0) 2020.01.29
[BOJ] 12783. 가장 긴 증가하는 부분 수열 3  (0) 2020.01.29

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

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

이 문제는 최소 신장 트리(MST)를 사용하여서 풀 수 있다. 완전 탐색으로도 그냥 풀 수 있다는데 다음에 풀어봐야겠다.

나는 크루스칼 알고리즘을 사용해서 풀었다.

 

 

1. 먼저 BFS로 각 섬에 번호를 붙인다.

2. 각 섬들 간 만들 수 있는 최단 거리의 직선 다리를 다시 BFS로 만들어 본다.

섬이 4개라고 했을 때, 1에서 2, 1에서 3, 1에서 4, 2에서 3, 2에서 4, 3에서 4로 가는 다리를 만들어주면 된다.

(다리 길이가 2 이상이 아니라면 만들 수 없다)

(직선 다리를 만들기 위해서 각 방향마다 쭉쭉 그 방향으로 이동한다.)

3. 다리를 만들 수 있다면 다리 길이와 함께 연결된 두 섬 번호를 벡터에 넣어준다.

4. 모든 다리를 구했으면 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 만들어준다.

 

 

크루스칼 알고리즘을 간단히 설명하면

간선들을 가중치를 기준으로 오름 차순 정렬한 후에

가중치가 제일 작은 것부터 연결되지 않은 간선들을 순차적으로 선택해나가는 알고리즘이다.

그리고 정점이 n 개라면 간선의 개수는 n-1개이므로 선택한 간선이 n-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
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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
int map[10][10];
int island[10][10];
int p[7];
vector<pair<int, pair<int, int>>> vt;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int getParent(int a) {
    if (p[a] == a) return a;
    return p[a] = getParent(p[a]);
}
 
 
void unionSet(int a, int b) {
    int rootA = getParent(a);
    int rootB = getParent(b);
    p[rootA] = rootB;
}
 
 
//u번 섬에서 v번 섬으로 가는 직선 최단 거리를 구한다.
void getMinDist(int u, int v) {
    queue < pair<int, int>> q;
 
    //u번 섬에 있는 칸들을 모두 큐에 넣는다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (island[i][j] == u) {
                q.push(make_pair(i, j));
            }
        }
    }
 
    int mindist = 10;
    int x, y;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            int dist = 0;
 
            //한방향으로 계속 이동
            while (true) {
                //범위를 넘어간 경우
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) break;
                //같은 섬인경우 더 탐색하지 않는다.
                if (island[nx][ny] == u) break;
 
                if (island[nx][ny] == v) {
                    //v번섬인 경우 최소거리와 비교후 더 탐색하지 않는다.
                    if (dist > 1 && mindist > dist) mindist = dist;
                    break;
                }
                else if (island[nx][ny] == 0) {
                    //바다인 경우 거리증가하고 이동
                    dist++;
                    nx += dx[k];
                    ny += dy[k];
                }
                else {
                    //다른 섬인 경우 더 탐색하지 않는다.
                    break;
                }
 
            }
        }
    }
 
    //최소거리가 초기값이 아니라면 벡터에 최소거리와 섬의 번호를 넣는다.
    if (mindist != 10) vt.push_back(make_pair(mindist, make_pair(u, v)));
}
 
 
void bfs(int x, int y, int num) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    island[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (map[nx][ny] == 0) continue;
            if (island[nx][ny] != 0) continue;
 
            q.push(make_pair(nx, ny));
            island[nx][ny] = num;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //섬에 번호를 붙인다.
    int num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //바다인 경우
            if (map[i][j] == 0) continue;
            //이미 번호를 붙인 경우
            if (island[i][j] != 0) continue;
 
            bfs(i, j, ++num);
        }
    }
 
 
    //위에서 번호를 붙인 num이 섬의 개수
    //각 섬들간의 만들수 있는 다리를 모두 만든다.
    for (int i = 1; i <= num - 1; i++) {
        for (int j = i + 1; j <= num; j++) {
            getMinDist(i, j);
        }
    }
 
    int size = vt.size();
 
    //거리를 기준으로 오름차순 정렬
    sort(vt.begin(), vt.end());
 
    //부모 배열 초기화(처음 부모는 자기 자신)
    for (int i = 1; i <= num; i++) p[i] = i;
 
    int sum = 0;
    int cnt = 0;
    int index = 0;
 
    int u, v, dist;
    //선택한 간선의 개수가 섬의개수 -1이 될때까지 간선을 선택한다.
    while (cnt < num - 1) {
        if (index == size) {
            //모든 섬을 연결하는 것이 불가능하다
            cout << -1 << "\n";
            return 0;
        }
 
        dist = vt[index].first;
        u = vt[index].second.first;
        v = vt[index].second.second;
 
        index++;
        if (getParent(u) == getParent(v)) {
            //이미 연결되어 있다.
            continue;
        }
        else {
            //연결되어 있지 않다면 합친다.
            unionSet(u, v);
 
            //연결된 간선의 수 증가
            cnt++;
 
            //다리 길이에 합쳐준다.
            sum += dist;
        }
    }
 
 
    cout << sum << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 5567. 결혼식  (0) 2019.11.13
[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06

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

 

17471번: 게리맨더링

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

www.acmicpc.net

 

먼저 그래프가 연결된 정점 정보로 주어지므로 vector 배열을 사용해서 인접 리스트를 구현해주었다.

adjlist[x] 에는 x에 연결된 정점들을 push해준다.

 

 

 

인구 차이가 가장 적게 나도록 선거구를 나누기 위해서는

DFS로 각 구역들을 선거구 1에 넣는 경우와 선거구 2에 넣는 경우를 모두 구해서 계산해본다.

선거구에 넣을 때, 나중에 BFS탐색 시 연결되어 있는지 확인하기 위해서 check배열을 추가적으로 사용하였다.

선거구 1에 넣는 경우는 check배열의 값을 true로 선거구 2에 넣는 경우는 check배열의 값을 false로 하였다.

 

 

 

각각의 경우에서 BFS탐색으로 한 선거구에 포함되어 있는 구역이 모두 연결되어 있는지 검사해줘야 하는데, 선거구 1과 선거구 2를 각각 BFS로 검사해줬다.

 

 

 

먼저 선거구 1을 검사할 때는 선거구에 있는 지역 하나를 처음에 큐에 넣고 연결된 구역들을 방문하며 방문 체크를 한다.

이때, check배열의 값이 false인 경우(선거구 2인 경우) 방문하지 못한다. BFS탐색이 끝난 후에 같은 선거구인데 방문하지 않았다면 한 선거구 내에 연결되지 않은 구역이 있다는 뜻이므로 false를 리턴한다.

 

 

 

마찬가지로 선거구 2를 검사할 때에도 check배열의 값이 true인 경우 (선거구 1인 경우)를 방문하지 않고 연결된 정점들을 모두 방문한다. 그리고 선거구 내에 방문하지 않은 구역이 있다면 false를 리턴한다.

 

 

 

 

위의 두 가지 경우에서 모두 false를 리턴하지 않았다면 두 선거구가 모두 각 선거구 내의 구역들이 연결되어 있다는 뜻이므로 true를 리턴하고 인구 차이를 계산한다.

 

 

 

 

/*구역의 수가 최대 10개이고, 각 구역의 인구수가 최대 100명이므로 두 구역의 인구 차이가 최대 1000명을 넘지 않으므로 정답을 저장할 ans변수의 초기값을 1000으로 해두었다 */

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n;
int ans;
 
//인구 수 저장
int arr[11];
 
//인접리스트
vector<int> adjlist[11];
 
//선거구 1
vector<int> vt1;
 
//선거구 2
vector<int> vt2;
 
//선거구 1인 경우 true, 선거구 2인 경우 false
bool check[11];
 
//BFS할때 방문체크 배열
bool visit[11];
 
 
bool bfs() {
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
 
    //선거구 1이 모두 연결되어 있는지 검사
    queue<int> q;
    q.push(vt1[0]);
    visit[vt1[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        //현재 구역과 연결된 구역들을 검사한다
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            //이미 방문한 경우
            if (visit[nx]) continue;
            //선거구 2인 경우
            if (!check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 1에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt1) {
        if (!visit[x]) return false;
    }
 
 
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
    
    //선거구 2가 연결되어 있는지 검사
    q.push(vt2[0]);
    visit[vt2[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            if (visit[nx]) continue;
            //선거구 1인경우
            if (check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 2에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt2) {
        if (!visit[x]) return false;
    }
 
    //각 선거구가 모두 연결되어 있다면 true를 리턴 
    return true;
}
 
 
void calc() {
    if (bfs()) {//각 선거구가 모두 연결되어 있다면 인구차이를 계산
        int sum = 0;
 
        //선거구 1과 선거구 2의 인구차이를 구한다.
        for (int x : vt1) sum += arr[x];
        for (int x : vt2) sum -= arr[x];
        if (sum < 0) sum = -sum;
 
        //최솟값보다 적다면 최솟값 갱신
        if (ans > sum) ans = sum;
    }
 
 
}
 
 
void solve(int index) {
    if (index > n) {
        //선거구에는 최소 1개의 구역이 포함되어야 한다
        if (vt1.size() == 0 || vt2.size() == 0) return;
        
        //인구차이를 계산
        calc();
        return;
    }
 
    //index구역을 선거구 1에 넣는 경우
    vt1.push_back(index);
    check[index] = true;
    solve(index + 1);
    check[index] = false;
    vt1.pop_back();
 
    //index구역을 선거구 1에 넣는 경우
    vt2.push_back(index);
    solve(index + 1);
    vt2.pop_back();
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    int cnt, x;
    for (int i = 1; i <= n; i++) {
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            cin >> x;
            adjlist[i].push_back(x);
        }
        
    }
 
    ans = 1000;
 
    solve(1);
 
    //ans값이 갱신되지 않았다면 두 선거구로 나눌수없는 경우이다.
    if(ans != 1000) cout << ans << '\n';
    else cout << -1 << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02

 

4월, 5월에도 상시 테스트 시험을 봤었는데 세 번째 시험에서 드디어 A+을 취득했다. 4월이랑 5월에는 둘 다 1문제씩만 풀어서 A만 두 개 있었다. 시험 응시 가능 횟수가 1년에 3번으로 제한되어 있어서 8월 시험이 나한테는 마지막 시험이었기 때문에 열심히 준비했었다.

근데 요즘에 시험 신청도 힘들어서 신청조차 못할까 봐도 무서웠는데 겨우 성공했다.

 

 

이번엔 꼭 A+을 따고자 두 문제를 시간 안에 연속으로 푸는 연습을 많이 했다. 항상 한 문제를 풀면 긴장이 풀려서인지 집중력이 풀려버렸기 때문이다. 그래서 두세 시간 안에 2문제씩 연속으로 풀었고 하루에 4 ~ 6문제 정도 풀었던 것 같다. 그러고 나서 풀었던 문제들을 블로그에 정리하며 복습했다. 어려웠던 문제는 다음날에 다시 블로그에 정리한 내용을 찾아보기도 했다.

문제를 풀 때는 아예 풀이가 30분에서 1시간 정도 안에 떠오르지 않으면 다른 분들의 풀이를 참고했고, 그냥 답이 잘 안 나오는 거라면 시간이 오래 걸려도 디버깅하면서 찾아냈다. 그래서 디버깅 연습이 많이 된 것 같다. 문제들은 풀었던 것도 다시 풀고 새로운 문제도 많이 풀었다. 그리고 조금 힘들 때는 일부러 쉬운 문제를 풀면서 자신감을 되찾았다...

 

 

4월에는 한 문제 푸는데만 두 시간 반이 걸렸고, 5월에는 한 문제는 일단 엄청 쉬워서 한 시간 안에 풀었는데 나머지 한 문제를 제대로 못 풀었다 그리고 이번에는 한 문제 한 시간, 다른 한 문제는 한 시간 반이 걸렸다. 둘 다 각각 30분씩은 허튼짓을 했다.... 물론 이것도 실력이겠지만...

그래도 일단 푸는 시간이 줄어들긴 하는 걸 보면 계속 풀면 실력이 늘긴 느는 것 같다.

5월은 쉽다는 사람이 많았는데 개인적으로 그때 못 풀었던 문제는 지금 생각해도 쉽지 않다... 

이번 8월 문제도 쉽다는 사람이 많았는데, A+을 따긴 했지만 개인적으로 쉽다고는 못하겠다. 어렵지는 않았던 것 같은데 마지막 시험이라 무거운 마음으로 봐서 그런지 쉽다고는 못 느꼈다. 그래도 자주 나오는 유형 느낌이긴 했다.

 

 

그리고 이번 시험에서 콘솔 창에 예제 input이 복사가 안됐는데, 이런 적이 처음이라 굉장히 당황했었다. 종종 안 되는 컴퓨터가 있다는 것 같다... 그래서 디버깅할 때 떨리는 손으로 하나하나 입력했었다. 이것만 아니었어도 30분에서 한 시간은 더 빨리 풀었을 것 같다...ㅂㄷㅂㄷ

문제 제출하는 부분에 주석으로 파일 오픈하는 코드가 있다던데 맨날 바로 지워버려서 못 봤다. 파일로 불러와서 디버깅하는 연습도 좀 해야 할 것 같다.

 

 

**시험 일정은 정해져있지 않다. 2019년 기준 3월, 4월, 5월, 8월, 9월하고 10월인가 11월인가 있었던 것 같다.

시험일정이 나오면 신청기간 전에 미리 신청 화면에 뜨기 때문에 자주 들어가서 확인해줘야 한다.

시험 신청 링크

https://swexpertacademy.com/main/sst/intro.do

 

SW Expert Academy

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

swexpertacademy.com

 

저작자표시

'후기' 카테고리의 다른 글

2019년 삼성 SDS 하계 대학생 알고리즘 특강 후기  (0) 2019.08.18

 

이번 삼성 SDS 하계 알고리즘 특강을 1 차수 때 수강하였다. 작년까지는 기본반/심화반이 나누어져 있었던 것 같은데 올해 초부터는 심화반만 진행하는 것 같다. 예전부터 방학 기간에 특강이 있는 것은 알고 있었지만 알고리즘 공부를 제대로 안 해봤기 때문에 입과 테스트를 통과할 자신이 없어서 신청하지 않았었다.

 

 

최근에는 공부를 좀 했기 때문에 신청을 해봤는데 이번에는 삼성 상시 SW 역량테스트 등급이 있으면 입과 테스트를 면제해주었다. 나는 A형이 있어서 면제를 받았다. (최근에는 A+ 취득했다ㅎㅎ)

입과 테스트 문제가 어렵다고 들은 것 같은데 다행이다.. 입과 테스트를 봤으면 통과 못했을지도 모르겠다...

 

 

 

 

 

 

입과 테스트는 면제받았지만 입과 확정은 아니라서 불안했는데 다행히 특강을 들을 수 있는 기회를 얻었다!

너무너무 듣고 싶어서 신청할 때 1 차수, 2 차수, 3 차수 모두 중복 체크했었다.

입과 대상자로 선정되면 위와 같은 메일이 온다! 메일 이외에도 입과 전까지 수시로 특강 관련 안내 문자를 주신다.

 

 

잠실과 완전 반대편에 살아서 2주 동안 왔다 갔다 하느라 힘들었지만 너무 유익한 특강이었다.

수업내용이 어렵다는 내용을 이전 후기로 봤기 때문에 걱정이 많았지만 못 풀더라도 불이익은 없다.

그리고 강사님들께서 설명이랑 풀이도 너무 잘해주신다.

 

 

수업에서 사용하는 언어는 C++이나 JAVA 인데 강사님이 사용하시는 언어에 따라 다르지만 설명을 듣는 데는 무리가 없다. 풀이 코드는 두 언어 모두 제공해주신다.

 

 

그리고 무엇보다 반강제로 하루 종일 코딩만 하기 때문에 실력이 늘지 않을 수가 없는 것 같기도 하고,

평소에 어려워서 스스로는 절대 공부하지 않았을 것들이나 기하 같은 어려운 부분을 배울 수 있어서 좋았다.

문제를 많이 못 풀더라도 노력한 만큼 많은 것을 배워갈 수 있는 것 같다.

 

 

그리고 점심을 제공해주는데 가격 상관없이 모든 메뉴를 무료로 먹을 수 있다!

맛은 소문대로 맛있었다ㅎㅎ

 

 

수료 테스트는 보통 특강이 끝난 주의 토요일에 보는 것 같은데 이번에는 금요일에 봤다.

나는 수업이 줄어들었기 때문에 너무 아쉬웠는데 시험 준비 기간이 줄어들어서 아쉬워하시는 분들도 많았다.

나는 어차피 통과할 자신이 없었으므로...ㅎㅎ

수료 테스트를 응시만 해도 일단 특강 수료는 인정된다! 물론 출석 기준도 통과해야 수료가 인정된다. 수업일수의 80%는 참석해야 됐었던 것 같다.

 

 

수료 테스트를 통과하면 삼성 SDS Professional을 취득하게 된다.

어렵기 때문에 통과하는 사람은 적은 듯하지만, 같이 들으신 분들 중에 잘하시는 분들 엄청 많으셨어서 통과하셨을 수도 있을 것 같다...

저작자표시

'후기' 카테고리의 다른 글

삼성 상시 SW 역량테스트 A형 후기 (2019년 8월 10일)  (0) 2019.08.18

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

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하

www.acmicpc.net

(수정)

이전의 풀이가 재채점 후에 시간 초과로 바뀌어서 다시 풀었다...

속력 s만큼 이동하면 안되고 결국 똑같은 범위 안에서 왔다 갔다 하는 것이므로 % 연산을 사용하여 이동을 단축시킬 수 있다. 즉 상하로 움직이는 경우에는 (r-1) * 2 , 좌우로 움직이는 경우에는 (c-1) * 2  만큼 움직일 때 원래 자리로 돌아온다.

 

//상하로 움직이는 경우

  if (d <= 2) {

        s = s % ((R-1) * 2);

  }

  else { //좌우로 움직이는 경우

        s = s % ((C-1) * 2);

  }

 

s만큼 이동하기 전에 이렇게 추가해줘서 pass하였다.

 

 

 

 

시뮬레이션 문제인데 상어들이 같은 곳에 있을 때의 처리를 해주는 게 어려웠다.

swea의 미생물 격리(?) 문제랑 살짝 비슷한 것 같다(미생물 격리가 더 어려움)

 

문제에서 주어지는 상어의 좌표, 속력, 방향, 크기의 정보와 추가적으로 살아있는지 여부를 확인할 bool변수를

구조체로 저장하여 관리하였다.

또한, 배열을 만들어서 상어의 위치에 상어의 인덱스를 저장하였다.(상어의 인덱스는 입력받은 순서다)

예를 들어 두 번째 상어의 좌표가 (1,3)이었다면 map [1][3] = 2

이런 식으로 저장하고 이동하거나 죽으면 다시 0으로 바꿔줬다.

 

이 배열을 활용하면 낚시왕이 상어를 잡을 때 낚시왕이 서있는 열만 배열에서 쭉 확인해주면 되므로

쉽게 구현할 수 있다.

 

두 마리 이상의 상어들이 같은 곳에 위치할 때에도 이 배열을 확인하였다.

이동할 좌표에 대해 다음과 같이 나눠서 처리해주었다.

r, c로 이동한다고 가정했을 때,

  • map[r][c] = 0 인 경우 ( 다른 상어가 없다)
    • 바로 map[r][c]에 현재 상어의 인덱스를 저장하면 된다.
  • map[r][c] > i 인 경우 ( 이전 인덱스의 상어가 와 있는 경우 ) // 인덱스 순서대로 진행하지면 동시에 일어나는 일이다!!
    • 현재 이동(같은 시간)에서 와 있는 상어이므로 크기를 비교 후 더 큰 상어가 해당 위치에 남아있게 된다.
  • map[r][c] < i 인 경우 ( 다음 인덱스의 상어의 번호가 있는 경우) 이전 이동(이전 시간)에서의 상어의 위치이다.
    • 다음 인덱스의 상어는 어차피 좀 이따 이동시켜줄 것이므로 그냥 첫 번째 경우처럼 바로 저장해주면 된다.

 

좀 더 자세한 설명은 코드의 주석 참고!

 
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int R, C, M;
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,1,-1 };
 
int map[101][101];
 
 
struct Shark {
    int r;
    int c;
    int s;
    int d;
    int z;
 
    //살아있는지 여부
    bool isAlive;
};
 
vector<Shark> vt;
 
int getShark(int c) {
    int getsize = 0;
 
    //낚시왕이 서있는 열의 행들만 검사한다.
    for (int i = 1; i <= R; i++) {
 
        //상어가 있으면
        if (map[i][c] != 0) {
 
            //크기를 받아오고
            getsize = vt[map[i][c]].z;
 
            //잡았으므로 죽인다.
            vt[map[i][c]].isAlive = false;
 
            //해당위치에서 지워준다.
            map[i][c] = 0;
 
            //가장 가까운 한마리만 잡음로 break
            break;
        }
    }
 
    //크기를 리턴
    return getsize;
}
 
void sharkMove() {
 
    int r, c, s, d, z;
    for (int i = 1; i <= M; i++) {
        //죽은 상어는 skip
        if (vt[i].isAlive == false) continue;
 
        r = vt[i].r;
        c = vt[i].c;
        s = vt[i].s;
        d = vt[i].d;
        z = vt[i].z;
 
        //다른 곳으로 이동할 것이므로 원래 있던 자리를 0으로 넣어준다.
        //이전 index의 상어가 현재 상어의 자리에 와 있지 않은 경우에만 0으로 초기화
        if (map[r][c] == i) {
            map[r][c] = 0;
        }
 
        
        //s를 줄여준다.
        if (d <= 2) {
            s = s % ((R-1) * 2);
        }
        else {
            s = s % ((C-1) * 2);
        }
        
 
        //스피드(s)만큼 d방향으로 이동
        for (int j = 0; j < s; j++) {
            r += dx[d];
            c += dy[d];
 
            //범위를 넘어가는 경우
            if (r < 1 || c < 1 || r > R || c > C) {
                if (d == 1 || d == 3) {
                    d += 1;
                }
                else {
                    d -= 1;
                }
 
                //범위 안으로 하나 들어오고
                r += dx[d];
                c += dy[d];
 
                //j는 다시 빼준다.(한 번 잘못 움직인 것 이므로)
                j--;
            }
 
        }
 
        //변경된 좌표와 방향을 상어 정보에 새로 저장
        vt[i].r = r;
        vt[i].c = c;
        vt[i].d = d;
 
 
        //이동한 곳에 다른 상어가 없다면 바로 저장
        if (map[r][c] == 0) {
            map[r][c] = i;
        }
        else if (map[r][c] < i) {
            // 이전 인덱스의 상어가 있는 경우에는 크기가 더 큰 상어가 더 작은 상어를 잡아먹는다.
 
            int tmp = vt[map[r][c]].z;
            if (z > tmp) {
                //현재 인덱스의 상어가 더 큰 경우 원래 있던 상어를 잡아먹는다.
                vt[map[r][c]].isAlive = false;
                map[r][c] = i;
            }
            else {
                //현재 인덱스의 상어가 더 작은 경우 잡아먹힌다.
                vt[i].isAlive = false;
            }
        }
        else {
            //현재 인덱스보다 뒷순서의 상어라면 어차피 이동할 것이므로 그냥 덮어쓴다.
            map[r][c] = i;
        }
 
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> R >> C >> M;
 
 
    //상어의 수가 0인 경우는 바로 0을 출력하고 종료
    if (M == 0) {
        cout << 0 << '\n';
        return 0;
    }
 
    int r, c, s, d, z;
 
    //index를 1부터 시작해주기 위해서 0번째에 아무거나 넣어놓는다.
    vt.push_back({ 0,0,0,0,0 });
    for (int i = 1; i <= M; i++) {
        cin >> r >> c >> s >> d >> z;
 
        //상어 정보를 벡터에 넣는다.
        vt.push_back({ r,c,s,d,z,true });
 
        //배열에 위치한 상어의 index를 저장
        map[r][c] = i;
    }
 
    int ans = 0;
    //C만큼 실행
    for (int i = 1; i <= C; i++) {
        ans += getShark(i);
        sharkMove();
    }
 
    cout << ans << "\n";
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 별 찍기 - 10  (0) 2019.08.31
[BOJ] 1655. 가운데를 말해요  (2) 2019.08.30
[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13
[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13

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

 

SW Expert Academy

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

www.swexpertacademy.com

이 문제에서 어려운 부분은두 개 이상의 군집이 하나의 셀에 모이는 경우인 것 같다.

어떻게 처리를 해줘야하나 한참 고민을 했었고, 처음엔 틀렸었다...ㅎ

 

이 부분을 처리해주기 위해서 먼저 군집들의 정보를 저장하기 위해 구조체를 만들어줬다.

군집 정보에는 x, y 좌표, 미생물 수(cnt), 방향(dit), 그리고 추가적으로 미생물 수 합을 저장하는 변수 sum을 만들었다.

그리고 배열을 만들어서 배열의 x, y좌표에는 해당 위치에 있는 군집의 번호를 기록해줬다.

매시간마다 위치는 바뀌기 때문에 배열의 값도 바뀌어야 하는데 그냥 헷갈지않게 배열 전체를 -1로 초기화해버렸다.

 

이동할 위치의 값이 -1(초기값)인 경우에는 아무 군집도 존재하지 않으므로 바로 그 위치로 이동한다.

그렇지 않은 경우에는, 기록되어 있는 인덱스를 이용해서 해당 위치에 있는 군집의 미생물 수와 현재 군집의 미생물 수를 비교해준다.

 

현재 미생물 수(cnt)가 더 큰 경우에는 배열의 값을 현재 군집의 번호로 바꿔주고 이전 군집의 미생물 수의 합(sum의 값)을 현재 미생물 수의 합에 더해준다. 그리고 이전 군집의 cnt와 sum은 0으로 만들어줌으로써 없애준다. 반대의 경우에도 비슷한 방식으로 처리해준다.

 

sum 변수를 추가적으로 써주는 이유는 3개이상의 군집이 하나의 셀에 모일 수 있기 때문이다.

위와 같은 상황에서 또 다른 군집이 같은 위치에 왔을 때, 이미 있는 군집의 cnt와 비교를 해줘야 하기 때문이다

즉, 합쳐진 값인 sum과 비교를 하면 안된다. 그리고 다시 새로 온 군집의 cnt가 더 큰 경우에는 이전 군집의 sum(앞에서 합쳐진 두 개의 군집의 미생물수)를 현재 군집의 sum에 더해주고, 이전 군집의 cnt와 sum은 다시 0으로 만들어준다.

 

 

이런 식으로 현재시간에 군집들의 이동이 모두 끝났다면

미생물 수(cnt)를 합쳐진 값(sum)으로 바꿔주면 된다.

그리고 이제 사라진 애들은 이동할 필요가 없기 때문에 cnt가 0인 애들은 continue 해준다

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int ans;
int n, m, k;
 
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };
int map[100][100];
 
struct Group {
    int x;
    int y;
    int cnt;
    int dir;
    int sum;
    Group(int x, int y, int cnt, int dir, int sum) : x(x), y(y), cnt(cnt), dir(dir), sum(sum) {}
};
 
vector<Group> vt;
 
 
void solve() {
    
    int time = 0;
 
    //m시간 동안 진행
    while (time++ < m) {
        memset(map, -1, sizeof(map));
 
        //모든 군집 이동
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            //사라진 군집은 이동하지 않는다.
            if (vt[i].cnt == 0) continue;
 
            //일단 값들 변수에 꺼내놓는다.
            x = vt[i].x;
            y = vt[i].y;
            cnt = vt[i].cnt;
            dir = vt[i].dir;
 
            //이동
            x += dx[dir];
            y += dy[dir];
 
 
            //이동한 좌표 새로 저장
            vt[i].x = x;
            vt[i].y = y;
 
 
            //약품이 칠해진 구역이면 미생물 수 반으로 감소 후 방향 반대로 전환
            if (x == 0 || y == 0 || x == n - 1 || y == n - 1) {
                vt[i].cnt /= 2;
                vt[i].sum /= 2;
                if (dir == 1 || dir == 3) {
                    vt[i].dir += 1;
                }
                else {
                    vt[i].dir -= 1;
                }
            }
            else {
                //약품이 칠해지지 않은 구역인 경우
                //이동한 곳에 아무도 없으면 현재 군집 번호를 저장
                if (map[x][y] == -1) {
                    map[x][y] = i;
                }
                else {
                    //이동한 곳에 이미 다른 군집이 있다
 
                    //이미 있는 군집의 미생물 수가 더 큰 경우
                    if (cnt < vt[map[x][y]].cnt) {
                        //현재 군집의 미생물 수의 합을 합쳐주고
                        vt[map[x][y]].sum += vt[i].sum;
 
                        //현재 군집은 없애준다.
                        vt[i].cnt = 0;
                        vt[i].sum = 0;
                    }
                    else {
                        //현재 군집의 미생물 수가 더 큰 경우
 
                        //이전 군집의 미생물 수 합을 현재 군집의 합에 더해주고
                        vt[i].sum += vt[map[x][y]].sum;
 
                        //이전 군집은 없애준다.
                        vt[map[x][y]].cnt = 0;
                        vt[map[x][y]].sum = 0;
 
                        //현재 군집의 번호를 새로 저장해준다.
                        map[x][y] = i;
                    }
 
                }
 
            }
 
 
 
        }
 
 
        //모든 군집의 이동이 끝났으면 합쳐진 미생물의 합을 군집의 미생물 개수로 바꿔준다.
        for (int i = 0; i < k; i++) {
            vt[i].cnt = vt[i].sum;
        }
 
    }
 
    //남은 미생물의 수를 세준다.
    for (int i = 0; i < k; i++) {
        ans += vt[i].cnt;
    }
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        vt.clear();
 
        cin >> n >> m >> k;
 
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            cin >> x >> y >> cnt >> dir;
            vt.push_back(Group(x, y, cnt, dir, cnt));
        }
 
        solve();
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 5650. [모의 SW 역량테스트] 핀볼 게임  (0) 2019.08.07
[SWEA] 1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2019.08.07
[SWEA] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06

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

 

SW Expert Academy

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

www.swexpertacademy.com

빈칸인 모든 칸으로부터  상하좌우 네 방향으로 모두 출발해보고 점수를 구하면된다. 그렇게 나온 점수 중 최댓값이 정답이다.

 

게임을 시작했으면 이동한 칸에 따라 처리해주면 된다.

 

1. 범위를 넘어간 경우(벽에 부딪힌 경우)에는 점수를 얻고 방향 전환 후에 바로 다음 칸으로 이동한다.

2. 출발 위치로 돌아오면 게임 종료

3. 블랙홀(-1)이면 게임 종료

4. 빈칸인 경우 계속 방향대로 이동

5. 블록인 경우(1~5)에는 각 블록의 방향에 맞게 방향을 전환해주고 점수를 얻는다.

6. 웜홀인 경우 같은 번호의 반대편 웜홀로 이동

 

 

웜홀의 경우에는 다음과 같이 x,y좌표를 가지는 벡터를 배열에 저장해서 구현하였다.

예를 들어 5번 웜홀의 좌표는 wormhole[0][0]과 wormhole[0][1]에 각각 들어있고, 6번 웜홀은 wormhole[1][0]과 wormhole[1][1]에 각각 들어있다. 게임판 배열에 들어있는 값에서 5를 빼준 값을 wormhole 배열의 인덱스로 사용하면 된다. (ex. 6번 웜홀의 인덱스는 1번)

 

wormhole 0(5번)

1(6번)

 2(7번) 3(8번) 4(9번) 5(10번)
0 (x,y) (x,y) (x,y) (x,y) (x,y) (x,y)
1 (x,y) (x,y) (x,y) (x,y) (x,y) (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
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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int n, ans;
int map[100][100];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
 
vector<pair<int, int>> wormhole[5];
 
void start(int x, int y, int dir) {
 
    int point = 0;
    int nx = x;
    int ny = y;
    while (true) {
 
        //이동
        nx += dx[dir];
        ny += dy[dir];
 
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
            point++;
 
            //반대 방향으로 바꿔준다.
            if (dir == 0 || dir == 1) {
                dir += 2;
            }
            else {
                dir -= 2;
            }
 
            //다음이동으로 바로 넘어감
            continue;
        }
 
 
        //출발위치로 돌아오면 게임 종료
        if (x == nx && y == ny) {
            break;
        }
 
        //블랙홀에 빠지면 게임 종료
        if (map[nx][ny] == -1) {
            break;
        }
 
        
        //빈칸이면 계속이동
        if (map[nx][ny] == 0) continue;
 
 
        //블록인 경우
        if (map[nx][ny] == 1) {
            if (dir == 0 || dir == 1) {
                dir += 2;
            }
            else if (dir == 2) {
                dir = 1;
            }
            else {
                dir = 0;
            }
 
            point++;
        }
        else if (map[nx][ny] == 2) {
            if (dir == 1) {
                dir = 3;
            }
            else if (dir == 2) {
                dir = 0;
            }
            else if (dir == 3) {
                dir = 2;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 3) {
            if (dir == 0) {
                dir = 3;
            }
            else if (dir == 1) {
                dir = 2;
            }
            else if (dir == 2) {
                dir = 0;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 4) {
            if (dir == 0) {
                dir = 2;
            }
            else if (dir == 1) {
                dir = 0;
            }
            else if (dir == 2) {
                dir = 3;
            }
            else {
                dir = 1;
            }
 
            point++;
        }
        else if (map[nx][ny] == 5) {
            dir = (dir + 2) % 4;
            point++;
        } else if (map[nx][ny] >= 6 && map[nx][ny] <= 10) {
            //웜홀인 경우
            int num = map[nx][ny] - 6;
 
            //0번에 있는 좌표와 같으면 1번에 있는 좌표로 이동
            if (wormhole[num][0].first == nx && wormhole[num][0].second == ny) {
                nx = wormhole[num][1].first;
                ny = wormhole[num][1].second;
            }
            else { //1번에 있는 좌표와 같은 경우이므로 0번에 있는 좌표로 이동
                nx = wormhole[num][0].first;
                ny = wormhole[num][0].second;
            }
        }
    }
 
    //점수의 최대값을 저장
    if (ans < point) ans = point;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        ans = 0;
        for (int i = 0; i < 5; i++) {
            wormhole[i].clear();
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                
                //웜홀이면 벡터 배열에 저장
                if (map[i][j] >= 6 && map[i][j] <= 10) {
                    wormhole[map[i][j] - 6].push_back(make_pair(i, j));
                }
            }
        }
 
 
        //모든 빈칸에서 네방향으로 출발
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0) continue;
 
                for (int k = 0; k < 4; k++) {
                    start(i, j, k);
                }
 
            }
        }
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2382. [모의 SW 역량테스트] 미생물 격리  (0) 2019.08.08
[SWEA] 1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2019.08.07
[SWEA] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2019.08.07
[SWEA] 2112. [모의 SW 역량테스트] 보호 필름  (0) 2019.08.07
[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기  (0) 2019.08.06

+ Recent posts

티스토리툴바