연구소 3

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.25 초 (하단 참고) 512 MB 13337 3607 2123 25.304%

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

1
2
3
4
5
6
7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

1
2
3
4
5
6
7
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

1
2
3
4
5
6
7
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

풀이

입력으로 주어진 바이러스의 갯수는 M개보다 크거나 같다.

따라서 바이러스의 갯수에서 M개를 골라서 활성화시킬 바이러스를 고른다. 그리고 바이러스를 퍼트린다. 모든 칸에 바이러스를 퍼트릴 수 있다. 이때, 바이러스를 모든 칸에 퍼트리는데 걸리는 최소 시간을 구하는 문제이다.

나의 풀이는 다음과 같다.

  • 바이러스의 위치를 확인하여 리스트에 넣는다.
  • 조합을 통해서 이 리스트에서 m개의 바이러스만 선택한다.
  • m개의 바이러스가 선택되면, 바이러스를 퍼트린다.
  • 퍼트리는 과정은 bfs 탐색을 통해 진행한다.
  • 이를 copy 한 배열에 퍼트림으로써 원본 배열을 유지한다.

하지만, 문제에서 제공하는 테스트 케이스 1과 7만 맞고 나머지는 맞지 않았다.

조합을 통해서 구하는 건 맞는데, 바이러스를 퍼트리고 그 과정에서 활성 바이러스와 비활성 바이러스를 구분하는 부분의 구현이 조금 어려웠다. 그래서 거기서 틀린 것으로 추측된다.

처음 접근한 나의 코드는 다음과 같다.
[나의 Code]

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/19
* 연구소3.
* 삼성 기출.
*/
public class Problem17142 {
private static int min = Integer.MAX_VALUE;
private static int n, m;
private static int[][] map;
private static ArrayList<Virus> list;
private static int[] comArr;
private static int[][] distance;
private static boolean[][] visit;
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, 1, 0, -1};

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] in = br.readLine().split(" ");
n = toInt(in[0]);
m = toInt(in[1]);

map = new int[n][n];
distance = new int[n][n];
list = new ArrayList<>();
int index = 0, r;
for (int i = 0; i < n; i++) {
in = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = toInt(in[j]);
//if (map[i][j] == 1) map[i][j] = -1;
if (map[i][j] == 2) list.add(new Virus(index++, i, j));
}
}

r = list.size();
comArr = new int[m];
combination(r, m, 0, 0);

System.out.println(min == Integer.MAX_VALUE? -1 : min);
}

private static void combination(int k, int r, int index, int target) {
if (r == 0) {
print();
return;
}

if (target == k) return;

comArr[index] = target;
combination(k, r - 1, index + 1, target + 1);
combination(k, r, index, target + 1);
}

// 여기서 visit, distance 배열 초기화.
private static void print() {
int[][] copy = new int[n][n];
visit = new boolean[n][n];
LinkedList<Virus> q = new LinkedList<>();


for (int index : comArr) {
Virus virus = list.get(index);
q.add(new Virus(virus.index, virus.x, virus.y));
visit[virus.x][virus.y] = true;
//distance[virus.x][virus.y] =-2;
//copy[virus.x][virus.y] = -2;
}

while (!q.isEmpty()) {
Virus cur = q.remove();

for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];

if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (visit[nx][ny]) continue;

if (map[nx][ny] == 0) {
q.add(new Virus(-1, nx, ny));
//copy[nx][ny] = map[cur.x][cur.y] + 1;
distance[nx][ny] = distance[cur.x][cur.y] + 1;
visit[nx][ny] = true;
}

}

}


for (int i = 0; i < list.size(); i++) {
Virus virus = list.get(i);
if (!visit[virus.x][virus.y]) {
distance[virus.x][virus.y] = -3;
}
}

for (int index : comArr) {
Virus virus = list.get(index);
distance[virus.x][virus.y] = -2;
}

/* for (int a : comArr) System.out.print(a + " : " + list.get(a) + " ");
System.out.println();*/

int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (result < distance[i][j]) result = distance[i][j];
//System.out.print(distance[i][j] + " ");
}
//System.out.println();
}

if (result < min) min =result;
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Virus {
int index;
int x;
int y;

Virus(int index, int x, int y) {
this.index = index;
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "Virus{" +
"x=" + x +
", y=" + y +
'}';
}
}
}

바이러스를 퍼트리는 과정에서 감이 잘 잡히지 않아서 다른 풀이를 참고했다.

참고한 풀이는 규글님의 블로그이다.

풀이 순서는 다음과 같다.

  1. 입력을 받으면서 바이러스가 나오면 리스트를 통해 바이러스의 정보를 저장한다.
  2. 총 바이러스의 갯수에서 m개 만큼의 바이러스를 선택한다.(조합 사용)
  3. m개의 바이러스를 선택했으면, bfs 탐색을 이용해서 바이러스를 퍼트린다.
  4. 선택된 m개의 바이러스를 큐에 넣는다.
  5. bfs
    • copy 배열을 만든다.
    • 조합에서 선택되지 않은 바이러스는 비활성 바이러스로 -9로 표시한다.
    • 벽인 부분은 -1로 표시한다.
    • 조합을 통해 선택된 바이러스는 활성 바이러스로 -2로 표시한다.
    • 큐에서 바이러스를 하나씩 빼면서, 네 방향을 탐색하며 퍼트릴 수 있는 만큼 퍼트리며, copy 배열을 채운다.
    • 범위를 벗어나거나 방문한 적이 있거나 벽이거나 활성 바이러스의 경우는 건너뛴다.
    • 위의 조건에서 걸리지 않은 경우에는 빈칸이거나 비활성 바이러스인 경우이다. 이때는 큐에 넣어주고, 빈칸인 경우에는 이전까지 온 거리 + 1을 copy 배열의 위치에 넣어준다.
    • 비활성 바이러스인 경우에는 copy 배열을 갱신하지 않고 -9인 채로 유지한다.
    • copy 값이 0이 아닌 경우에는 이미 그 공간을 방문한 적이 있는 것이므로 최소값으로 갱신한다. copy 값보다 이전까지 온 거리가 더 작다면 그 작은 값으로 갱신한다.
  6. bfs 탐색이 끝나고 바이러스를 퍼트리지 못한 지점이 하나라도 존재하면 그 바이러스 조합은 종료한다.
  7. copy 배열을 탐색하며 가장 큰 값을 찾는다. 이 값은 바이러스를 퍼트리는데 걸린 총 시간을 의미한다.
  8. 그리고 copy 배열에서 0보다 큰 값이 하나라도 존재한다면 이는 바이러스를 퍼트린 시간을 계산할 수 있음을 의미한다. 따라서 result 값과 비교하여 가장 작은 값을 result 값에 갱신하도록 한다.
  9. copy 배열에서 0보다 큰 값이 하나라도 존재하는 것은 바이러스를 퍼트린 시간이 존재함을 뜻한다. 0보다 큰 값이 없다는 것은 이미 바이러스가 벽이 아닌 공간에 모두 퍼져 있어 더 이상 퍼트릴 공간이 없다는 것을 뜻하며 시간은 0이 된다.
  10. 0보다 큰 값이 하나라도 존재하면 퍼트린 시간이 존재하므로 이때는 더 작은 값을 max에 저장한다.

주의할 점은 활성 바이러스가 비활성 바이러스 칸에 가면 비활성 -> 활성이 된다는 것이다.

벽 : -1

비활성 바이러스 : -9

활성 바이러스 : -2

이렇게 설정하고 문제를 접근한다.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/20
* 연구소 3.
* 삼성 기출.
* <p>
* 초기
* 0 : 빈칸
* 1 : 벽
* 2 : 바이러스 위치.
*/
public class Problem17142_3 {
private static int n;
private static int result;
private static int[][] map;
private static int[] set;
private static ArrayList<Virus> list;
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
// 상하좌우.

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] in = br.readLine().split(" ");
n = toInt(in[0]);
int m = toInt(in[1]);

// 초기화.
init();
// 입력을 받으면서 바이러스의 위치를 리스트에 저장한다.
for (int i = 0; i < n; i++) {
in = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = toInt(in[j]);
if (map[i][j] == 2) list.add(new Virus(i, j, 0));
}
}

set = new int[m];

// 총 바이러스의 개수에서 m개를 뽑는 조합을 진행한다.
combination(list.size(), m, 0, 0);
System.out.println(result == Integer.MAX_VALUE ? -1 : result);
}

private static void init() {
map = new int[n][n];
list = new ArrayList<>();
result = Integer.MAX_VALUE;
}

private static void combination(int N, int R, int index, int target) {
// 조합을 만든 경우, 그 조합을 기반으로 bfs 를 진행한다.
if (R == 0) {
bfs();
return;
}

if (target == N) return;

set[index] = target;
combination(N, R - 1, index + 1, target + 1);
combination(N, R, index, target + 1);
}

/*
* bfs() 탐색을 진행해 바이러스를 퍼트린다.
* 벽은 -1로 초기화.
* 비활성 바이러스는 -9로 초기화.
* 바이러스는 -2로 초기화.
* */
private static void bfs() {
int[][] copy = new int[n][n];
LinkedList<Virus> q = new LinkedList<>();
boolean[][] visit = new boolean[n][n];

// 활성 바이러스와 비활성 바이러스를 나눠서 처리한다.
// 비활성 바이러스는 -9로 초기화한다.
// 활성 바이러스는 -2로 초기화 하면서 큐에 넣고 방문 여부를 체크한다.
for (int i = 0; i < list.size(); i++) {
boolean flag = false;
for (int index : set) {
// 활성 바이러스인 경우.
if (i == index) flag = true;
}

Virus virus = list.get(i);

if (!flag) {
copy[virus.x][virus.y] = -9;
} else {
copy[virus.x][virus.y] = -2;
q.add(virus);
visit[virus.x][virus.y] = true;
}
}

// 벽 초기화.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 1) copy[i][j] = -1;
}
}

// bfs 탐색을 진행한다.
while (!q.isEmpty()) {
Virus cur = q.remove();
int time = cur.time;

for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];

// 범위를 벗어나거나 방문한 적이 있거나 해당 정점이 벽이거나 혹은 활성 바이러스인 경우에는 건너뛴다.
if (!isRange(nx, ny) || visit[nx][ny] || copy[nx][ny] == -1 || copy[nx][ny] == -2) continue;

// 빈칸이거나 비활성 바이러스인 경우, 방문 여부를 체크하고 큐에 넣는다.
// 이유는 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 -> 활성 상태로 바뀌기 때문이다.
if (copy[nx][ny] == 0 || copy[nx][ny] == -9) {
visit[nx][ny] = true;
q.add(new Virus(nx, ny, time + 1));

// 빈칸인 경우, 처음 방문한 곳이기 때문에 해당 정점에 지금가지 걸린 시간 + 1을 넣어준다.
if (copy[nx][ny] == 0) {
copy[nx][ny] = time + 1;
} else {
// 이미 값이 있는 경우는 다른 바이러스에 의해서 이미 퍼지고 시간이 적혀 있는 것을 의미한다.
// 따라서 최소 시간으로 갱신이 가능하면 갱신한다.
// 왜냐하면 바이러스는 동시에 인접한 네 칸으로 퍼지기 때문이다.
// 현재 정점에 적힌 시간보다 지금까지 걸린 시간 + 1이 작으면 지금까지 걸린 시간 + 1로 갱신한다.
if (copy[nx][ny] > time + 1) copy[nx][ny] = time + 1;
}
}
}
}

int max = Integer.MIN_VALUE;

if (isFinish(copy)) return;

// 0보다 큰 값에 대해서 확인을 하며 가장 큰 값을 찾아 max 에 저장한다
// 이는 바이러스를 모두 퍼트리는 데 걸린 시간을 구한다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (copy[i][j] < 0) continue;
if (max < copy[i][j]) max = copy[i][j];
}
}

// true : 바이러스를 퍼트리는 데 걸린 시간 중 최소 값을 구한다.
if (isCompleted(copy)) {
if (max < result) result = max;
} else {
result = 0;
}
}

// 이미 벽과 충분한 바이러스로 꽉 차고 애초에 빈칸이 없는 경우에는 false 값을 반환한다.
// 따라서 바이러스가 퍼지는 데 걸리는 시간은 없다. 0이다.
// 0보다 큰 값이 하나라도 존재한다면 바이러스가 퍼진 시간을 계산할 수 있기 때문에 true 반환.
private static boolean isCompleted(int[][] copy) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (copy[i][j] > 0) return true;
}
}
return false;
}

// 바이러스가 모든 곳에 퍼졌는지 확인한다.
// 모든 곳에 퍼졌다면 false 반환.
// 퍼지지 않은 곳이 한 곳이라도 존재하면 true 반환.
private static boolean isFinish(int[][] copy) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (copy[i][j] == 0) return true;
}
}
return false;
}

// 범위 안에 들어오는 지 확인한다.
private static boolean isRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Virus {
int x;
int y;
int time;

Virus(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
}

Comment and share

미세먼지 안녕!

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 7939 4272 2890 53.988%

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

img

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
    • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
    • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
    • 공기청정기에서는 바람이 나온다.
    • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

img

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

img

인접한 네 방향으로 모두 확산이 일어난다.

img

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

img

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

아래의 일이 1초 동안 일어난다.

  1. 미세먼지가 모든 칸에서 동시에 일어난다. -> bfs 탐색을 통해서 진행한다.
  2. 공기 청정기의 위쪽은 반시계 방향, 아래쪽은 시계 방향으로 바람이 분다. 이로 인해 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다. -> 이 부분은 그대로 구현을 하면 된다.
  3. 공기 청정기의 위치로 들어간 미세먼지는 정화된다.
  4. 공기 청정기가 움직인 뒤, 바뀐 map 배열을 업데이트 해준다.
  5. T초가 지난 후 방에 남아있는 미세먼지의 양을 출력한다.

문제에서 주의해야 할 점은 원본 배열이 바뀌면 안되기 배열을 복사해서 copy를 이용해서 미세먼지를 확장시키고 난 뒤의 배열을 원본 배열에 업데이트 해준다. 그리고 공기 청정기가 돌면서 정화한 뒤의 배열을 다시 원본 배열에 업데이트 시키는데, 이때 공기 청정기의 바람이 지나가면서 바뀐 부분만 업데이트 하도록 한다.

문제에서 공기 청정기의 바람에 의해 정화된 후, 바뀐 배열을 원본 배열에 업데이트 시킬 때, 변경된 부분만 업데이트 시키려 하는 과정에서 조건문을 ||로 줘야 하는데 && 로 하나를 주면서 20분 정도 해맸다…

풀이

조금 더 시간을 줄일 수 있는 방법이 있다. 위의 풀이에서는 visit 배열을 두어 방문 여부를 체크하고 결국, 다시 초기화 하는 형태였는데 이는 불필요하다.

굳이 bfs 탐색을 하면서 visit 배열을 사용하지 않는 것이다. 어차피 미세먼지의 확산은 동시에 일어나기 때문에 이로 인해서 방문한 곳은 또 방문하게 된다. 따라서 이를 아예 고려하지 않으면 문제가 되지 않는다.

  1. 미세먼지가 있는 곳은 큐에 넣는다.
  2. bfs 탐색을 통하여 미세먼지를 확장한다.
  3. 공기 청정기가 움직이며 바람을 통해 순환시킨다.
  4. 위의 과정을 t 동안 반복하고, 미세 먼지의 양의 합을 구한다.

다만, 주의할 점은 원본 배열이 변경되기 때문에 copy 배열을 만들어서 작업한 후, 원본 배열에 업데이트 시켜줘야 한다는 점이다.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/17
* 미세먼지 안녕!
* 삼성 기출.
* 시뮬레이션 + 구현.
*/
public class Problem17144Re {
private static int r, c, t;
private static int[][] map;
private static Node[] cleaners;
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, 1, 0, -1};

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] in = br.readLine().split(" ");
r = toInt(in[0]);
c = toInt(in[1]);
t = toInt(in[2]);

map = new int[r][c];
cleaners = new Node[2];
int index = 0;
for (int i = 0; i < r; i++) {
in = br.readLine().split(" ");
for (int j = 0; j < c; j++) {
map[i][j] = toInt(in[j]);
// 공기 청정기의 위치를 저장한다.
if (map[i][j] == -1) cleaners[index++] = new Node(i, j);
}
}

solve();
}

private static void solve() {
for (int i = 0; i < t; i++) {
spreadDust(); // 미세 먼지를 확장한다.
spreadCleaner();
}

getResult();
}

// 미세먼지를 확장시킨다.
// 이를 위해서 copy 배열을 두고 큐에서 꺼내면서 미세 먼지가 동시에 확장되는 것을 구현한다.
private static void spreadDust() {
// 모든 미세먼지는 동시에 확장되기 때문에 copy 배열을 두어 map 배열에서 꺼내면서 확장시킨다.
int[][] copy = new int[r][c];

// 미세 먼지가 존재하는 칸을 큐에 넣는다.
LinkedList<Node> q = new LinkedList<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] > 0) q.add(new Node(i, j));
}
}

// 큐에서 꺼내면서 인접한 네 방향을 검사하면서 미세 먼지를 확장한다.
// 이 과정은 동시에 일어난다.
while (!q.isEmpty()) {
Node dust = q.remove();
int x = dust.x, y = dust.y;

// 확산되는 양.
int amountOfDust = map[x][y] / 5;
int count = 0;

// 인접한 네 방향 검사.
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];

// 범위 검사.
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

// 공기 청정기가 아닌 곳은 미세먼지를 확장시킬 수 있으므로, 미세먼지를 확장시킬 수 있는 공간의 갯수를 구한다.
// 그리고 미세먼지가 있는 곳에 확산되는 양을 더해준다.
if (map[nx][ny] != -1) {
count++;
copy[nx][ny] += amountOfDust;
}
}

copy[x][y] += map[x][y] - amountOfDust * count;
}

copyDust(copy);
}

// map <- copy
private static void copyDust(int[][] copy) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
map[i][j] = copy[i][j];
}
}

/*System.out.println("== 미세 먼지 확장 ==");
print();*/
}

// 공기 청정기가 바람을 통해서 순환한다.
// !!! 여기는 t가 아니라 공기청정기가 2칸 차지하니까 2여야 함..
private static void spreadCleaner() {
int[][] copy = new int[r][c];
for (int i = 0; i < 2; i++) {
Node cleaner = cleaners[i];
int x = cleaner.x;
int y = cleaner.y + 1;

// 오른쪽으로 끝까지 이동한다.
while (y < c - 1) {
copy[x][y + 1] = map[x][y];
y++;
}

// 반시계 방향의 경우.
if (i == 0) {
// 위로 올라간다.
while (x > 0) {
copy[x - 1][y] = map[x][y];
x--;
}
} else { // 시계 방향의 경우.
while (x < r - 1) {
copy[x + 1][y] = map[x][y];
x++;
}
}

// 왼쪽으로 끝까지 이동한다.
while (y > 0) {
copy[x][y - 1] = map[x][y];
y--;
}

// 반시계 방향의 경우.
if (i == 0) {
while (x < cleaner.x - 1) {
copy[x + 1][y] = map[x][y];
x++;
}
} else { // 시계 방향의 경우.
while (x > cleaner.x + 1) {
// !!! -1로 했었는데, 그게 아니라 +1로 해야 함
// 아래에서 위로 올라가기 때문이다.
copy[x - 1][y] = map[x][y];
x--;
}
}
}

copyCleaner(copy);
}

// 공기 청정기의 바람이 순환하는 경로만 map 배열로 업데이트 시켜준다.
private static void copyCleaner(int[][] copy) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 || i == r - 1 || j == 0 || j == c - 1 || i == cleaners[0].x || i == cleaners[1].x)
map[i][j] = copy[i][j];
}
}

/*System.out.println("== 공기청정기 동작 후 ==");
print();*/
}

private static void getResult() {
int sum = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] > 0) sum += map[i][j];
}
}

System.out.println(sum);
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

// 확인용.
private static void print() {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}

static class Node {
int x;
int y;

public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}

참고

  • [백준 미세먼지 안녕!](

Comment and share

아기 상어

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16449 6615 3776 36.991%

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이

bfs + 시뮬레이션인 것 같다.

풀이

  1. 2차원 배열을 통해 입력을 받는다.
  2. 상어가 존재하는 9일 경우, 상어의 위치를 저장한다. 그리고 이후에 bfs 탐색을 하면서 조건을 검사하기 위해 상어가 있던 위치는 0으로 바꿔준다.
  3. 최초의 shark 객체를 상어의 위치와 distance 0으로 만들어준다. size = count = 2이다. 초기 상어의 크기가 2이기 때문이다.
  4. 상어가 가장 가까운 물고리를 찾기 위해서 bfs 를 시작한다. 초기에 상어를 큐에 넣어준다. 상어의 distance는 INF 값으로 할당한다. 이유는 최단 거리를 찾아서 업데이트 할 것이기 때문!
  5. 큐에서 상어를 네 방향을 탐색한다. 범위를 벗어나지 않고, 방문한 적이 없는 곳을 큐에 넣는다.
  6. 5번을 반복하면 큐에 여러 값들이 들어가므로 조건 검사를 제대로 할 수 있게 된다.
  7. 조건을 검사한다.
    • 상어의 distance에는 최단 거리가 담기는데, 현재 위치의 거리가 더 크다면? 이때는 bfs를 중단한다. 최단 거리보다 더 움직인 것이기 때문에 최단 거리는 구해졌다.
    • 상어의 크기인 size 보다 큰 물고기는 먹을 수 없으므로 다음 물고기를 확인하기 위해 skip 한다.
    • 물고기가 존재하면서, 상어의 크기보다 작은 물고기인 경우에는 상어가 먹을 수 있다.
      • 상어가 이 물고기까지 온 거리가 그 전에 알고 있던 거리보다 작다면 최단 거리로 갱신한다.
      • 그렇지 않고 이 물고기까지 온 거리와 그 전에 알고 있던 거리가 같다면 더 위에 있는 물고기를 먹는다.
      • 그러한 물고기가 여러 마리라면 더 왼쪽에 있는 물고기를 먹는다.
      • 물고기를 먹는 것은 상어가 그 물고기가 있는 곳에 위치하는 것으로 먼저 표현을 한다.
  8. bfs 탐색이 끝나고 나서 상어의 distance 가 바뀌었는지 확인한다. 바뀌었다면, 상어의 위치가 바뀌고 distance 값도 바뀌었다. 이는 상어가 그 물고기의 위치를 찾아서 먹었음을 의미한다.
  9. 상어가 물고기를 먹으러 이동한 거리를 time에 더하고, count 값을 감소시킨다. 이는 상어가 자신의 크기만큼 물고기를 먹기 위함이다.
  10. count == 0인 경우를 확인한다. true 라면 상어가 자신의 크기만큼 물고기를 다 먹었고 상어의 크기는 1 증가한다. 그리고 count는 size로 초기화 해준다.
  11. 8번의 조건을 확인하면서 상어의 distance 값이 바뀌지 않았다면, 상어가 물고기를 먹을 수 있는 물고기를 찾지 못해 bfs가 그대로 종료됐음을 의미한다. 따라서 반복문을 빠져나온다.
  12. time 값을 반환한다.

[Code]

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
package SW_Study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
* created by victory_woo on 2020/04/15
* 아기 상어.
* 시뮬레이션 + bfs
* 난이도 높음... 어려움...
* 다시 풀어보기!
*/
public class Problem16236 {
private static final int INF = Integer.MAX_VALUE;
private static int n;
private static int[][] map;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = toInt(br.readLine());

map = new int[20][20];

// 상어의 위치를 저장하기 위한 변수를 선언한다.
int sharkX = 0, sharkY = 0;

for (int i = 0; i < n; i++) {
String[] in = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = toInt(in[j]);
// 상어의 위치를 저장한다.
if (map[i][j] == 9) {
sharkX = i;
sharkY = j;

// 상어가 이동할 때, 최초 상어의 위치는 중요하지 않기 때문에
// 상어가 최초 위치했던 곳은 빈곳으로 바꿔준다.
map[i][j] = 0;
}
}
}
System.out.println(solve(sharkX, sharkY));
}

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

private static int solve(int x, int y) {
int time = 0; // 이동하는 데 걸리는 시간.
int size = 2; // 상어의 크기. 이동할 때마다 상어의 크기와 비교해야 함.
int count = size;
Fish shark = new Fish(x, y, 0);
// 최단 거리를 찾아야 하기 때문에 최초 위치는 상어의 위치로 시작한다.

// 상어가 가장 가까운 물고기를 찾기 위해서 bfs 탐색을 한다.
while (true) {

// 방문 여부 체크.
boolean[][] visit = new boolean[20][20];
LinkedList<Fish> q = new LinkedList<>();
visit[shark.x][shark.y] = true;
q.add(new Fish(shark.x, shark.y, 0));
shark.distance = INF;

while (!q.isEmpty()) {
Fish cur = q.remove();

// 계속 진행하다 보면 현재 위치의 거리가 우리가 찾은 최단 거리보다 커지는 경우가 존재한다.
// bfs 탐색을 중단한다.
// 거리가 최단 거리보다 멀어졌다는 의미는 더이상 확인할 물고기가 없다는 걸 뜻한다.
if (cur.distance > shark.distance) break;

// 상어의 크기보다 큰 물고기가 있다면 해당 물고기는 skip 한다. 즉, 건너뛰고 다른 물고기를 탐색한다.
if (map[cur.x][cur.y] > size) continue;

// 물고기가 존재하고, 현재 상어보다 물고기의 크기가 작다고 하면 먹을 수 있다.
if (map[cur.x][cur.y] != 0 && map[cur.x][cur.y] < size) {
// 이 물고기까지 온 거리가 그 전에 알고 있던 거리보다 작다면 최단 거리를 갱신한다.
// shark 를 현재 위치로 바꿔준다.
if (cur.distance < shark.distance) {
shark = cur;
} else if (cur.distance == shark.distance) {
// 거리가 같은 물고기가 존재한다면
// 더 위에 있는 물고기를 먹는다.
if (cur.x < shark.x) {
shark = cur;
} else if (cur.x == shark.x && cur.y < shark.y) {
// 같은 높이에 있다면 더 왼쪽에 있는 물고기를 먹어야 한다.
// 따라서 y 좌표가 더 작은 물고기를 먹는다.
shark = cur;
}
}
// 가장 가까운 물고기를 찾았기 때문에 continue 로 아래 네 방향으로 진행하는 탐색을 skip 한다.
continue;
}

for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];

if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (visit[nx][ny]) continue;

visit[nx][ny] = true;
q.add(new Fish(nx, ny, cur.distance + 1));
}
}

// INF 가 아닌 경우 물고기를 찾은 경우.
// 이동 거리르 증가하고, 물고기의 갯수를 줄여준다.
if (shark.distance != INF) {
time += shark.distance;
count--;
if (count == 0) {
size++;
count = size;
}

// 먹은 물고기는 0으로 지워준다.
map[shark.x][shark.y] = 0;

} else {
break;
}
}

return time;
}


private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Fish {
int x;
int y;
int distance; // 상어가 이동하는 데 걸린 거리.(거리가 곧 시간)

Fish(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
}
}

Comment and share

주사위 윷놀이

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2885 1052 652 31.976%

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

img

  • 처음에는 시작 칸에 말 4개가 있다.
  • 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
  • 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
  • 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
  • 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

풀이

글쎄,? 어떻게 풀어야 할까

일단, 예상 로직은 다음과 같다.

  • 그림이 그래프 형태를 이루고 있고, 얻을 수 있는 점수의 최댓값
  • 말을 골라서 이동시켜야 함.
  • Dfs + 백트래킹을 사용하면 될 것 같다.

하지만, 고려할 점

  • 그림을 어떻게 표현할 것인가?
  • 말을 선택하는 부분!
  • 이동 전에 이동할 칸에 말이 있는지 여부를 확인해야 한다.

buddev 님의 블로그를 참고했다.

구현 포인트

파란 점일 때, 아닐 때를 구분해서 리스트를 구현해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
static class Node {
int score; // 해당 칸의 점수.
int red; // 빨간 화살표로 이동할 경우, 다음 점.
int blue; // 파란 화살표로 이동할 경우, 다음 점.
boolean isBlue; // 파란 점인지 여부.

Node(int score, int red) {
this.score = score;
this.red = red;
}
}

문제에서 칸의 번호와 점수가 동일한데, 같은 번호가 있는 칸이 두개씩 있는 경우가 존재한다.
따라서 겹치는 번호들에 한해서 번호를 바꿔서 지정했다.

이를 디버깅하고 난 후, 내가 생각한 풀이를 적는다.

  1. 윷놀이 판의 가장 바깥 라인은 2의 배수로 채운다. -> 문제와 똑같이 간다.
  2. 꺾이는 부분, 파란 점으로 인한 지름길이다. 바깥 라인과 값이 중복되기 때문에 다른 값으로 대체한다.
  3. 중복을 허용하는 수열을 이용해서 주사위가 나오는 값 별로 올 수 있는 말의 경우를 모두 구한다.
  4. 모두 구했으면, now 배열, check 배열을 초기화 하고 말을 움직인다.(move() 호출)

[Code]

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* created by victory_woo on 2020/04/15
*/
public class sw17825Re {
private static final int TEN = 10;
private static int[] permutation, now, step;
private static boolean[] check;
private static Node[] map;
private static int max;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] in = br.readLine().split(" ");

permutation = new int[TEN];
step = new int[TEN];
map = new Node[43];

for (int i = 0; i < TEN; i++) step[i] = toInt(in[i]);
setDice();
getPermutation(0);
System.out.println(max);
}

// 파란 점이 있는 부분에 대해서 처리한다.
// 바깥 라인과의 중복된 값이 존재하기 때문에 인덱스를 다르게 주었고, 값은 그대로 저장했다.
// 또한, 빨간 점으로 된 다음 좌표를 저장한다.
private static void setDice() {
for (int i = 0; i <= 40; i += 2) map[i] = new Node(i, i + 2);

map[10].isBlue = map[20].isBlue = map[30].isBlue = true;

map[10].setBlue(11);
map[20].setBlue(17);
map[30].setBlue(31);

map[11] = new Node(13, 13);
map[13] = new Node(16, 15);
map[15] = new Node(19, 25);

map[17] = new Node(22, 19);
map[19] = new Node(24, 25);

map[31] = new Node(28, 33);
map[33] = new Node(27, 35);
map[35] = new Node(26, 25);

map[25] = new Node(25, 37);

map[37] = new Node(30, 39);
map[39] = new Node(35, 40);

map[42] = new Node(0, 42);
}

private static void getPermutation(int depth) {
if (depth == 10) {
now = new int[4];
check = new boolean[43];
move();
return;
}

for (int i = 0; i < 4; i++) {
permutation[depth] = i;
getPermutation(depth + 1);
}
}

private static void move() {
int score = 0;
for (int i = 0; i < TEN; i++) {
// 말을 움직여서 말이 도착한 지점의 값을 구한다.
// 말이 step 만큼 움직이도록 horseMove() 함수를 호출한다.
// end 값은 말이 주사위 step 만큼 움직이고 난 뒤의 칸.
int end = horseMove(permutation[i], step[i]);
if (end == -1) return;
now[permutation[i]] = end; // 현재 말이 있는 칸을 업데이트 한다.
score += map[end].score;
}

if (max < score) max = score;
}

// now : 윷놀이 판 위에서 말이 위치한 인덱스.(말이 있는 윷놀이 판의 인덱스)
private static int horseMove(int horse, int step) {
// 몇 번째 말이 움직일 것인지 뽑는다.
// 즉, 이동할 말을 정한다.
int temp = now[horse];

// 말이 step 만큼 움직인다.
// 첫 좌표이면서 파란 점이라면 파란 점을 temp 에 저장한다.
// 그게 아니라면 말이 이동할 다음 좌표(빨간 점의 위치)를 찾아 temp 에 저장한다.
for (int i = 0; i < step; i++) {
if (i == 0 && map[temp].isBlue) {
temp = map[temp].blue;
continue;
}

temp = map[temp].red;
}

// 도착 지점에 도착하지도 않았는데, 방문한 곳을 또 방문한 경우.
if (temp <= 40 && check[temp]) {
return -1;
} else {
check[now[horse]] = false;
check[temp] = true;
return temp;
}
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Node {
int score;
int blue;
int red;
boolean isBlue;

public Node(int score, int red) {
this.score = score;
this.red = red;
}

public void setBlue(int blue) {
this.blue = blue;
}

public void setRed(int red) {
this.red = red;
}

}
}

이 문제는 주사위를 저렇게 구현해 낼 수 있느냐 없느냐의 싸움인 것 같다.
풀고나면 어렵지 않지만, 저렇게 생각해 내는 연습이 필요한 것 같다.
더 열심히 하자~
뿅!

Comment and share

  • page 1 of 1
Author's picture

VictoryWoo

기록을 통해 사람들과 공유하는 것을 좋아합니다.


Android Developer