https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
풀이
'상어별 이동 방향 결정' -> '이동' -> 냄새 뿌리기 및 상어 겹치는 거 처리 -> 냄새 감소
를 1번 상어만 남을 때까지 반복하면 됩니다.
1) 상어별 이동 방향 결정
- 각 상어 별로 방향 우선순위별로 순회하면서, 냄새가 0인 경우 > 냄새가 자기 자신인 경우 > 나머지인 경우를 찾습니다. 저는 i번째 상어가 현재 j 방향으로 움직일 때 다음 움직임의 우선순위 k를 3차원 int 배열에 저장하였습니다.
- 크게 어려울 거 없습니다.
2) 이동 및 냄새 뿌리기, 중복 상어 처리
- 문제 지문에서 상어는 '동시에' 이동한다고 했습니다. 그러나, 우리가 코드를 구현할 때는 상어 번호 i에 대해 1부터 M까지 for문을 돌테니, 현재 상어 및 냄새를 저장하는 배열에서 이를 처리하면 앞 상어의 움직임이 뒷 상어의 움직임에 영향을 줄 수 있으니, 배열을 복사하여 이동 및 냄새를 뿌려주고, 이를 다시 복사해야 합니다.
3) 냄새 감소
- 냄새를 어떻게 저장했는지 설명하도록 하겠습니다. 냄새는 1) 남은 유효시간, 2) 누구의 냄새 인지를 저장해야 합니다. 클래스를 만들어서 저장할 수도 있겠으나, 사실 좀 번거롭고 구현도 길어지므로, 각 위치마다 '1000*(남은 시간)+(상어 번호)'로 저장했습니다. 상어는 최대 400마리(N <= 20이고 M <= N^2)이므로 겹치지 않으며, 남은 시간 k는 최대 1000이기에 전체 정수가 int 범위에서 벗어나지도 않습니다.
- 그래서, 냄새가 있으면(>0), 만약 냄새가 2000 이상이면(== 남은 시간이 2초 이상) 1000을 빼주고, 그 외의 경우(==남은 시간이 1초) 해당 위치의 냄새를 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
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
|
import java.io.*;
import java.util.*;
public class Main {
static int[] dr = { 0, -1, 1, 0, 0 };
static int[] dc = { 0, 0, 0, -1, 1 };
static int[][][] priorities;
static int[][] sharks, smells;
static boolean[] isDead;
static int[] rows, cols, dirs;
static int alive, N, M, k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
priorities = new int[M+1][5][4];
sharks = new int[N][N];
smells = new int[N][N];
isDead = new boolean[M+1];
rows = new int[M+1];
cols = new int[M+1];
dirs = new int[M+1];
alive = M;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
sharks[i][j] = Integer.parseInt(st.nextToken());
if (sharks[i][j] > 0) {
rows[sharks[i][j]] = i;
cols[sharks[i][j]] = j;
}
}
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
dirs[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= 4; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < 4; k++) {
priorities[i][j][k] = Integer.parseInt(st.nextToken());
}
}
}
int t = 0;
while (t <= 1000) {
t++;
move();
smellDesc();
if (alive == 1) break;
}
System.out.println((t==1001)? -1: t);
}
// 이동 및 이전 자리에 냄새 뿌리기, 겹치는 상어 삭제
static void move() {
// 현재 이동 후 냄새를 저장할 배열
int[][] tempSmells = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tempSmells[i][j] = smells[i][j];
}
}
// 현재 이동한 상어를 저장할 배열
int[][] tempSharks = new int[N][N];
for (int i = 1; i <= M; i++) {
if (isDead[i]) continue;
chooseDir(i); // 우선순위 방향 찾기
int r = rows[i], c = cols[i];
int nr = r + dr[dirs[i]], nc = c + dc[dirs[i]];
tempSmells[r][c] = 1000*k + i; // 냄새 뿌리기
// 상어가 있는 경우
if (tempSharks[nr][nc] > 0) {
// 잡아먹을 수 있는 경우
if (tempSharks[nr][nc] > i) {
isDead[tempSharks[nr][nc]] = true;
alive--;
tempSharks[nr][nc] = i;
} else {
isDead[i] = true;
alive--;
}
// 상어가 없는 경우
} else {
tempSharks[nr][nc] = i;
}
// 위치 갱신
rows[i] = nr;
cols[i] = nc;
}
// 동시에 모든 상어가 움직인 후, 냄새 및 상어 위치 갱신
smells = tempSmells;
sharks = tempSharks;
}
static void chooseDir(int i) {
int tempVal = Integer.MAX_VALUE, tempDir = 5;
int r = rows[i], c = cols[i];
for (int k = 0; k < 4; k++) {
int nr = r + dr[priorities[i][dirs[i]][k]], nc = c + dc[priorities[i][dirs[i]][k]];
if (!isIn(nr, nc)) continue;
int tempSmell = smells[nr][nc] % 1000;
if (tempVal > 0 && tempSmell == 0) {
tempVal = tempSmell;
tempDir = priorities[i][dirs[i]][k];
} else if (tempVal == Integer.MAX_VALUE && tempSmell == i) {
tempVal = tempSmell;
tempDir = priorities[i][dirs[i]][k];
}
}
dirs[i] = tempDir;
}
// 냄새 감소시키기
static void smellDesc() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (smells[i][j] > 0) {
if (smells[i][j] > 2000) smells[i][j] -= 1000;
else smells[i][j] = 0;
}
}
}
}
static boolean isIn(int r, int c) {
return !(r < 0 || r >= N || c < 0 || c >= N);
}
}
|
cs |
'PS > Implementation' 카테고리의 다른 글
| 백준 20061번: 모노미노도미노 2 (Java) (0) | 2022.07.15 |
|---|---|
| 백준 23288번: 주사위 굴리기 2 (Java) (0) | 2022.07.14 |
| 백준 2174번: 로봇 시뮬레이션 (Java) (0) | 2022.06.30 |
| 백준 17106번: 빙고 (Java) (0) | 2022.06.29 |
| 백준 4991번: 로봇 청소기 (Java) (0) | 2022.06.27 |