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.acmicpc.net/problem/17406

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계

www.acmicpc.net

회전 연산을 사용하는 모든 경우를 구해주고 배열을 회전시켜줘야 하는 문제이다.

즉, 완전 탐색 + 시뮬레이션이다.

 

 

회전 정보는 구조체로 만들어서 벡터에 저장하여 관리하였다.

그리고 문제에서 (1,1)부터 시작하므로 r과 c 좌표는 각각 1씩 빼주었다.

정답의 최댓값은 행의 최대길이 50 * 칸의 최댓값 100으로 5000정도이지만 그냥 안전하게 10000 정도를 초기값으로 넣어놨다.

 

 

 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

라는 문제 조건에 따라 사용할 회전 연산 순서를 모두 정해준다.

순서를 정할 때마다 새로운 배열을 만들어서 배열을 회전시켜준 상태로 넘겨준다.

그리고 k개 만큼 순서를 모두 정했다면 그때의 배열의 값(행의 합 중 최솟값)을 구해준다.

 

 

회전을 시킬 때는 밑의 그림에서 파란 네모로 묶인 애들을 각각 for문을 사용해서 옮겨줬다.

즉 for문을 4번 사용하여 회전시켰다.

(r-s, c-s)를 시작점으로 배열을 회전시켜줄 건데 이 부분의 값은 따로 빼놓는다.

그리고 첫번째 for문에서 밑의 칸들을 하나하나 올려준다.

그리고 다시 두 번째 for문에서 오른쪽 칸들을 옆으로 하나하나 옮겨준다.

옮겨주다가 맨 윗줄을 이동시켜줄 때는 마지막 칸을 옮기면 안 되고 처음에 빼놨던 (r-s, c-s) 값을 넣어줘야 한다.

 

 

s가 2인 경우에는 2인 경우와 1인 경우 모두 구해줘야 하기 때문에 s 값을 줄여가면서 배열을 모두 돌려주면 된다.

2부터 시작해서 r-2, c-2를 시작점으로 배열을 회전시키고 난 후에 s 값을 1 감소시켜서

다시 r-1, c-1을 시작점으로 다시 배열을 회전시켜주면 된다.

마찬가지로 s가 더 큰 값일 경우에도 s 수만큼 배열을 회전시키면 된다.

 

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int ans;
int n, m, k;
bool check[6];
 
struct Info {
    int x;
    int y;
    int size;
    Info(int x, int y, int size) : x(x), y(y), size(size) {}
};
 
vector<Info> vt;
 
void move(int index, int map[50][50]) {
    //index번째 회전 연산의 정보를 가져온다.
    int x = vt[index].x;
    int y = vt[index].y;
    int s = vt[index].size;
 
    while (s > 0) {
 
        int tmp = map[x - s][y - s];
 
        //첫번째 열 이동
        for (int i = x - s; i < x + s; i++) {
            map[i][y - s] = map[i + 1][y - s];
        }
 
        //마지막 행 이동
        for (int j = y - s; j < y + s; j++) {
            map[x + s][j] = map[x + s][j + 1];
        }
 
        //마지막 열 이동
        for (int i = x + s; i > x - s; i--) {
            map[i][y + s] = map[i - 1][y + s];
        }
 
        //첫번째 행 이동
        for (int j = y + s; j > y - s + 1; j--) {
            map[x - s][j] = map[x - s][j - 1];
        }
 
        //마지막 칸
        map[x - s][y - s + 1] = tmp;
        s--;
    }
 
}
 
 
void mapcpy(int map[50][50], int newmap[50][50]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
}
 
 
//각 행의 합 중 최솟값을 구한다.
void calc(int map[50][50]) {
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            sum += map[i][j];
        }
        if (ans > sum) ans = sum;
    }
}
 
 
void solve(int index, int map[50][50]) {
    if (index == k) {
        //회전 연산을 모두 사용하였으면 계산
        calc(map);
        return;
    }
 
 
    for (int i = 0; i < k; i++) {
        //i번을 이미 사용
        if (check[i]) continue;
 
        int newmap[50][50];
        mapcpy(map, newmap);
 
        //사용 표시후에 배열을 회전시킨다.
        check[i] = true;
        move(i, newmap);
 
        //배열을 회전 시킨 상태에서 다음 회전을 사용하는 경우를 구한다.
        solve(index + 1, newmap);
 
        //다른 회전을 사용하는 경우를 위해 다시 사용 표시 없앤다.
        check[i] = false;
 
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> k;
    ans = 10000;
    int map[50][50];
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int r, c, s;
    for (int i = 0; i < k; i++) {
        cin >> r >> c >> s;
        r--;
        c--;
        vt.push_back(Info(r, c, s));
    }
 
 
    solve(0, map);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1655. 가운데를 말해요  (2) 2019.08.30
[BOJ] 17143. 낚시왕  (0) 2019.08.18
[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

www.acmicpc.net

안전 영역을 구해줄 것이므로 물에 잠기지 않는 부분에 대해서 BFS를 해준다.

그리고 BFS를 한 횟수가 안전영역의 수가 된다.

 

 

지역의 높이 범위가 1부터 100인데 시간을 줄이기 위해서 지역의 정보를 처음에 입력을 받을 때 지역 높이의 최댓값을 구해놓는다.

그리고 1부터 높이의 최댓값 -1 까지만큼 비가 오는 경우를 모두 구해주면 된다.

높이의 최댓값 이상으로 비가 오는 경우는 안전 영역이 0이 되기 때문이다.

그리고 각 경우에서의 안전 영역을 정답(최댓값)과 비교해서 저장한다.

 

주의할 점은 

아무 지역도 물에 잠기지 않을 수도 있다.

라고 문제 밑부분 노트에 쓰여있는데 이 경우는 안전 영역이 1이므로 정답의 초기값은 0이 아닌 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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n;
int maxh;
int ans;
int map[100][100];
bool check[100][100];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y, int h) {
 
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (check[nx][ny]) continue;
            if (map[nx][ny] <= h) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
        }
    }
 
}
 
void solve() {
 
 
    for (int h = 1; h < maxh; h++) {
        memset(check, false, sizeof(check));
        int safearea = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j]) continue;
                //높이가 더 낮은 곳은 물에 잠기므로 넘어간다
                if (map[i][j] <= h) continue;
 
                bfs(i, j, h);
                safearea++;
            }
        }
 
        if (ans < safearea) ans = safearea;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (maxh < map[i][j]) maxh = map[i][j];
        }
    }
 
 
    ans = 1;
    
    solve();
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17143. 낚시왕  (0) 2019.08.18
[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08

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

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지

www.acmicpc.net

BFS를 이용해서 푸는 문제이다.

 

인접한 칸이 바다인 경우에는 그 개수를 세주어서 빙산의 높이에서 빼주면 된다.

바다가 아닌 빙산인 경우에는 큐에 넣어주고 해당 빙산에 대해서도 탐색을 이어가면 된다.

 

 

BFS는 연결된 모든 칸을 방문하기 때문에 연결되지 않은 칸에 방문하기 위해서는 BFS를 새로 시작하여야 한다.

즉, bfs횟수가 1회일 때는 아직 모두 연결되어 있는 한 덩어리라는 뜻이므로 계속 시간을 늘려가며 bfs를 진행하고

BFS 횟수가 1번이 넘을 때는 빙산이 두 덩어리 이상이 됐음을 의미하므로 그때 시간을 출력해주고 탐색을 종료한다.

 

 

만약 다 녹았는데 빙산이 분리되지 않은 경우를 처리하기 위해서는 flag 변수를 둬서 bfs탐색이 한 번도 일어나지 않은 경우에 0을 출력해주고 종료하도록 해줬다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int map[300][300];
bool check[300][300];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (check[nx][ny]) continue;
 
            //인접한 칸이 바다인 경우 cnt증가
            if (map[nx][ny] == 0) {
                cnt++;
            }
            else {
                //빙산인 경우에는 큐에 넣어주고 계속 탐색
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            
        }
 
 
        //인접해 있는 바다의 수만큼 높이 줄어든다.
        map[x][y] -= cnt;
        //0보다 작아지지는 않는다.
        if (map[x][y] < 0) map[x][y] = 0;
 
    }
 
}
 
void solve() {
 
    int time = 0;
    while (true) {
        int cnt = 0;
        bool flag = false;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                //바다인 경우 continue
                if (map[i][j] == 0) continue;
                //이미 방문한 경우
                if (check[i][j]) continue;
 
                //빙산이 아직 있다.
                flag = true;
                bfs(i, j);
 
                //빙산의 덩어리 수
                cnt++;
            }
        }
 
        //전부 다 녹을 때까지 두덩어리 이상으로 분리되지 않는 경우
        if (!flag) {
            cout << 0 << '\n';
            return;
        }
 
 
        //두 덩어리 이상이 되었을 경우 시간을 출력하고 return(종료)
        if (cnt > 1) {
            cout << time << "\n";
            return;
        }
 
 
        //시간 증가
        time++;
 
        memset(check, false, sizeof(check));
    }
 
    
 
}
 
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];
        }
    }
 
    solve();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13
[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06

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

 

2234번: 성곽

문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을

www.acmicpc.net

  1. 이 성에 있는 방의 개수
  2. 가장 넓은 방의 넓이
  3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

를 구하는 문제이다. 이 문제는 bfs와 비트 마스크를 사용해서 풀었다.

 

 

먼저 1번과 2번문제에 대한 답을 먼저 구하였다.

방문하지 않은 모든 칸에 bfs를 사용하여 방문하고 bfs가 시작될 때마다(새로운 방이므로) 방 개수를 늘려준다.

그리고 bfs탐색을 할때마다 방문하는 칸의 개수를 세줘서 방의 넓이를 구하여 방의 넓이 중 최댓값을 구할 수 있다.

 

이 문제에서 bfs를 할 때 중요한 부분은 벽인지 아닌지 알아내야 한다.

 

 

벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

라고 문제 입력에서 주어지는데 이 부분이 힌트인 것 같다. 그림으로 나타내면 아래와 같다.

 

 

 

 

문제에서 주어진 예시 그림(맨 위 그림)의 왼쪽 끝칸(0,0)을 예시로 들어보면 아래 그림과 같다. 서쪽, 북쪽, 남쪽에 벽이 있기 때문에

1+2+8 = 11로 11이 문제 입력에서 주어진다. 11은 다시 이진수로 1011로 나타낼 수 있으므로 이를 이용해서 비트 마스크로 검사를 한다.

int dx[] = { 0,-1,0,1 };

int dy[] = { -1,0,1,0 };

먼저 방향 배열을 서, 북, 동, 남 순서로 해놓아야 한다. 그래야 1 << 0을 했을 때의 값이 1이므로 서쪽을 표현할 수 있고 1<<1 은 2로 북쪽을 표현할 수 있다.

그리고 검사할 칸과 & (1<<k)를 해서 해당 위치에 1을 가지고 있는지 검사한다. (k는 0부터 3으로 네 방향의 index)

1을 가지고 있는 경우(위의 연산 결과가 0이 아닌 경우)에는 벽이므로 해당 방향으로는 이동하지 않는다.

 

 

그리고 나중에 3번 문제를 해결하기 위해서플러드 필 알고리즘(연결 요소에 번호를 매김)을 사용한다. bfs를 할 때 현재 연결된 칸들에 방 번호를 매겨주고 각 방의 넓이 또한 cnt 배열에 저장해놓는다.

 

 

3번 문제를 해결하기 위해서는 다음과 같은 생각을 했다.

인접해있는 방과 현재 방의 넓이를 합쳤을 때의 최댓값이 하나의 벽을 제거했을 때의 결과와 마찬가지다.

아래 그림을 봤을 때 1번 방은 2번 방과 3번 방과 인접해있는데 3번 방과 인접해있는 벽 중 하나를 제거했을 때 최댓값을 얻을 수 있다.

 

 

코드로 구현하자면 다시 새로운 bfs를 이용한다. 이때 bfs에서는 아까 플러드 필 알고리즘을 사용하여 방 번호를 매긴 배열을 이용한다.

이동했을 때 같은 방인 경우에는 계속 큐에 넣고 방문 체크를 해주며 탐색을 이어가고 같은 방이 아닌 경우에는 현재 방의 칸수와 옆의 방의 칸수를 합친 값(위에서 저장한 cnt배열을 이용)을 저장하고 이 합쳐진 값들 중 최댓값이 정답이 된다.

 

1번 방에 대해 인접한 방에 대해서 모두 탐색을 해봤다면 다음 2번 방을 검사할 때는 다시 1번 방과 비교할 필요는 없다.

그러므로 bfs로 방문한 칸은 모두 다 체크해주면 된다.

 

 

역시 코드를 보는 게 가장 이해하기 쉬울 것 같다ㅎㅎ

순서는 main -> solve -> bfs 다음에 removeWall -> bfs2로 진행된다.

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int m, n;
int map[50][50];
int visit[50][50];
bool check[50][50];
int cnt[2500];
 
 
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
int bfs2(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int sum = 0;
    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 (check[nx][ny]) continue;
 
 
            //같은 방이면 큐에 넣고
            if (visit[nx][ny] == visit[x][y]) {
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            else { //다른 방이면 그 방과 합쳐졌을 때의 넓이를 저장
                int tmp = cnt[visit[x][y]] + cnt[visit[nx][ny]];
                if (sum < tmp) sum = tmp;
            }
 
        }
    }
 
    return sum;
 
}
 
void removeWall() {
    queue<pair<int, int>> q;
 
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j]) continue;
            int tmp = bfs2(i, j);
            if (sum < tmp) sum = tmp;
        }
    }
    
    cout << sum << '\n';
}
 
int bfs(int x, int y, int num) {
    int cnt = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visit[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            //해당 방향이 벽인 경우
            if (map[x][y] & (1 << k)) continue;
 
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visit[nx][ny]) continue;
 
            q.push(make_pair(nx, ny));
 
            //방 번호를 기록
            visit[nx][ny] = num;
            cnt++;
        }
 
    }
 
 
    //연결된 칸의 개수를 리턴(방의 넓이)
    return cnt;
}
 
void solve() {
 
    int maxcnt = 0;
    int roomcnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visit[i][j]) continue;
 
            //bfs출발할 때마다 방의 개수 늘어난다
            int tmp = bfs(i, j, ++roomcnt);
 
            //방 별로 넓이를 저장해놓는다.
            cnt[roomcnt] = tmp;
 
            //가장 넓은 방의 넓이
            if (maxcnt < tmp) maxcnt = tmp;
        }
    }
 
    //1번 답 출력
    cout << roomcnt << "\n";
 
    //2번 답 출력
    cout << maxcnt << "\n";
 
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    //1번과 2번 답을 구한다
    solve();
 
    //3번 답을 구한다
    removeWall();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05

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

 

11559번: Puyo Puyo

현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.)

www.acmicpc.net

시뮬레이션 카테고리에 넣었지만 BFS도 이용하는 문제이다.

BFS는 상하좌우로 연결되어 있는 같은 색의 뿌요를 찾기 위해 사용한다.

 

 

먼저 연쇄가 몇 번 일어났는지를 알아내야 하는 문제이기 때문에 연쇄가 일어나지 않을 때까지 터뜨리기를 반복해야한다.

 

 

각 반복에서는 뿌요가 있는 모든 칸에 대해서 BFS탐색을 통해 상하좌우로 연결된 같은 색의 뿌요가 네 개 이상 있는지 체크해준다. 있다면 해당 칸의 뿌요들을 터뜨려주고(.으로 만들어 준다) 연쇄가 발생했다는 뜻으로 true를 리턴한다.

문제 조건에 따라 여러 그룹의 뿌요가 터졌더라도 연쇄는 한 번 일어난 걸로 간주한다.

예를 들어, 전체 칸을 탐색할 때 R이 4개 이상 모여있었고 다른 곳에서 G가 4개이상 모여있어서 두 그룹이 터졌다고 해도 같은 턴에 터지는 애들은 한번 일어난 걸로 count 해준다.

 

 

모든 뿌요에 대해서 탐색을 해줬는데 flag가 false라면 (한 번도 연쇄가 발생하지 않았다면) 반복문을 break 해주고 정답을 출력해주면 된다.

 

flag가 true라면(연쇄가 적어도 한 번 이상 발생했다면) 떠있는 뿌요들을 바닥에 내려주고 연쇄가 일어난 횟수(정답)를 증가시킨다.

 

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
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
 
char map[12][6];
int check[12][6];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans;
 
void move() {
    for (int j = 0; j < 6; j++) {
        for (int i = 11; i >= 0; i--) {
            if (map[i][j] != '.') continue;
 
            //빈 칸(.)을 찾았으므로 위에 떠있는 애를 찾는다.
            bool flag = false;
            for (int k = i - 1; k >= 0; k--) {
                
                //떠있는애 발견
                if (map[k][j] != '.') {
                    //내려준다.
                    map[i][j] = map[k][j];
                    map[k][j] = '.';
                    flag = true;
                    break;
                }
            }
 
            //위에 떠있는게 없으면 다음 열을 검사한다.
            if (!flag) {
                break;
            }
        }
    }
}
 
bool bfs(int x, int y) {
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    
    q.push(make_pair(x, y));
    check[x][y] = true;
    int cnt = 1;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue;
            //방문 체크
            if (check[nx][ny]) continue;
            //같은 색인지 체크
            if (map[nx][ny] != map[x][y]) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
            cnt++;
        }
    }
 
 
    //같은 색의 뿌요가 4개이상 존재하면 모두 터진다.
    if (cnt >= 4) {
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (check[i][j]) map[i][j] = '.';
            }
        }
        
 
        return true;
    }
    else return false;
}
 
void solve() {
    
    
    while (true) {
 
        bool flag = false;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] == '.') continue; //빈칸
 
                //같은 색의 뿌요들이 4개이상 모여있어서 터지는지 검사
                if (bfs(i, j)) {
                    flag = true;
                }
 
            }
        }
 
        //더 이상 터질게 없다.
        if (!flag) break;
        else {
            //터졌으면 중력에 의해 뿌요들이 아래로 떨어진다.
            move();
 
            ans++;
        }
 
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string s;
    for (int i = 0; i < 12; i++) {
        cin >> s;
        for (int j = 0; j < 6; j++) {
            map[i][j] = s[j];
        }
    }
 
    solve();
 
 
    cout << ans << '\n';
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04

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

티스토리툴바