https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
절대절대 이 문제는 값을 독립적으로 관리하는게 중요하다.
최종값을 제외하고 변수의 수명을 짧게 관리하는게 이 문제의 고생을 줄일 수 있는 길!!
얕은 복사/깊은 복사에 엄청 호되게 당했다...
문제 풀이 자체도 그리 단순하지도 않다.
구현 사항을 정리하자면, 1. 상어가 물고기 먹음. 2. 물고기 이동. 3. 상어의 사냥 세 가지이다.
자료구조는 물고기의 구조체 배열(숫자가 작은 물고기가 이동해야하기에 필요했다.)과 지도 관리를 위한 2차원 배열을 사용하였다.
백트래킹/DFS가 사용되기에 뒤에서부터 풀이하자면
3. 상어는 방향이 있고 해당 방향으로는 격자를 벗어나지 않는 선에서 어디든지 이동할 수 있으며 이동 중의 물고기는 잡아먹지 않는다. 따라서 잡아먹을 수 있다면 전부 탐색을 해줘야한다.
2. 물고기의 이동은 현재 방향 기준 반시계방향으로 갈 수 있는 가장 가까운 곳을 가고 그 위치의 물고기와 위치를 바꿔준다.
이 과정에서 현재 물고기는 이동 가능한 위치와 방향의 값을 갱신해주고, 원래 있던 곳의 물고기는 위치만 갱신해준다.
1. 상어가 이동한 위치의 물고기 값을 추가하고, 갱신하고, 물고기가 존재하지 않음을 표시한다.
나의 경우엔 물고기 배열에선 null 처리, 지도에서는 -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
|
import java.io.*;
import java.util.*;
class Main {
static int[][] dirs = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } };
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int[][] map = new int[4][4];
Fish[] fishes = new Fish[16];
answer = 0;
for (int i = 0; i < 4; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++) {
int idx = Integer.parseInt(st.nextToken()) - 1;
int dir = Integer.parseInt(st.nextToken()) - 1;
fishes[idx] = new Fish(idx, dir, i, j);
map[i][j] = idx;
}
}
dfs(fishes, map, 0, 0, 0);
System.out.println(answer);
}
private static void dfs(Fish[] fishes, int[][] map, int row, int col, int sum) {
// << 새로운 물고기 상어 정보를 초기화 >>
Fish[] nextFish = new Fish[16];
for (int i = 0; i < 16; i++) {
Fish cur = fishes[i];
if (cur == null)
continue;
nextFish[i] = new Fish(i, cur.dir, cur.row, cur.col);
}
int[][] nextMap = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
nextMap[i][j] = map[i][j];
}
}
// << 상어한테 먹힘 >>
int target = nextMap[row][col];
int sharkDir = nextFish[target].dir;
nextMap[row][col] = -1;
nextFish[target] = null;
sum += (target + 1);
answer = Math.max(answer, sum);
// << 물고기 이동 >>
for (Fish fish : nextFish) {
if (fish == null)
continue;
int fishD = fish.dir;
int fishR = fish.row;
int fishC = fish.col;
int nextD = fishD;
int nextR = fishR;
int nextC = fishC;
// << 방향 정하기 >>
for (int d = 0; d < 8; d++) {
nextD = (fishD + d) % 8;
nextR = fishR + dirs[nextD][0];
nextC = fishC + dirs[nextD][1];
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4)
continue;
if (nextR == row && nextC == col)
continue;
break;
}
// << 위치 교환하기 >>
if (nextMap[nextR][nextC] == -1) {
nextFish[fish.idx].row = nextR;
nextFish[fish.idx].col = nextC;
nextFish[fish.idx].dir = nextD;
nextMap[nextR][nextC] = fish.idx;
nextMap[fishR][fishC] = -1;
} else {
target = nextMap[nextR][nextC];
nextFish[target].row = fishR;
nextFish[target].col = fishC;
nextFish[fish.idx].row = nextR;
nextFish[fish.idx].col = nextC;
nextFish[fish.idx].dir = nextD;
nextMap[nextR][nextC] = fish.idx;
nextMap[fishR][fishC] = target;
}
}
// 이동가능한 모든 곳에 상어 이동하기
for (int d = 1; d < 4; d++) {
int nextR = row + dirs[sharkDir][0] * d;
int nextC = col + dirs[sharkDir][1] * d;
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4)
break;
if (nextMap[nextR][nextC] != -1)
dfs(nextFish, nextMap, nextR, nextC, sum);
}
}
static class Fish {
int idx;
int dir;
int row;
int col;
Fish(int idx, int dir, int row, int col) {
this.idx = idx;
this.dir = dir;
this.row = row;
this.col = col;
}
}
}
|
cs |