Notice
Recent Posts
Recent Comments
Link
HwangHub
[Java/Simulation] 백준 21611. 마법사상어와 블리자드 본문
🤔 Intuition
바라는 게 많은 시뮬레이션 문제. 길을 잃지 않도록 변수명을 잘 선언하고, 로직을 잘 구성한 뒤 코드를 작성해야 할듯.
- 탐색은 정직하게 달팽이탐색으로 구현할 것.
- pull 또는 stretch 과정에서 temp 배열 인덱스를 복잡하게 운영하는 것보다는 1차원으로 차곡차곡 쌓아두고, 이를 고대로 다시 달팽이탐색으로 복붙하는게 편할 듯
- 연속되는 구슬을 터뜨리기 위해 좌표를 저장하는 건, 나중에 길이를 체크하고 되돌아가서 하나하나 터뜨리는 논리이므로 stack 자료구조가 적절할 듯
🔎 Algorithm & Complexity
- Algorithm : 시뮬레이션
- 시간복잡도 : O(N^4) : N^2 탐색 X 최악의 경우 stack에 N*N개 채워진 상태로 뒤로감기 → 480 ms
- 공간복잡도 : O(N^2) : 2차원 map 저장 + 최대 N^2 개를 저장하는 stack
👨🏻💻 Logic
메서드를 구현하여 시뮬레이션 흐름에 맞게 loop 태움
- 달팽이탐색 : 탐색 방향이 LEFT → DOWN → RIGHT → UP 이면서 해당 방향으로 탐색 개수가 1 1 2 2 3 3 4 4 … 흐름의 반복되는 패턴이므로 이를 이용하여 loop를 이용하여 구현함
- blizzard() : 재귀함수를 이용하여 d방향으로 s만큼 set map[y][x] = 0
- pull() : 배열에 공백이 없도록 상어 방향으로 당겨주는 메서드. 중력 구현처럼 map을 상어 위치부터 달팽이탐색 하면서 0이 아닌 값만 temp[] 배열에 차곡차곡 담아서, 이후 다시 달팽이탐색하면서 temp[] 값을 map에 붙여넣기
- bomb() : map을 달팽이탐색 하면서 연속된 구슬의 좌표를 stack에 차곡차곡 담으면서 진행. 연속된 구슬임을 판단하기 위해 구슬의 값을 peek이라는 변수에 담아둠.⇒ 한번이라도 터뜨린 적 있으면 return true / 없으면 return false 하도록 하여 pull & bomb 과정을 반복할 수 있게 함
- ⇒ 만약 연속되지 않는 구슬이 발견되면 stack의 size를 체크하여 4개 이상일 때 stack.pop()을 반복하면서 적재해 둔 좌표의 map 값을 0으로 set. || 만약 size가 4개 미만일 경우 stack을 그냥 비워줌. || 현재 구슬을 stack에 담고 달팽이탐색 재개
- stretch() : 반복되는 개수를 체크하는 cnt 변수와, 연속되는 구슬인지 여부를 판단하기 위한 peek 변수를 운영. 연속이 끊길 때마다 temp[] 값을 업데이트 하면서 진행. 연속된 구슬의 길이가 1개일 때에도 stretch가 발생하므로 temp에 대입할 때 index가 범위를 넘어가진 않는지 하나하나 체크할 필요 O
마지막으로... 코드가 반복되는 감이 없지 않지만 실전에서는 바로 떠오르지 않는 이상 그냥 이렇게 냅다 하는 편이다. 로직이 꼬이는 게 더 risky한 행동이기 때문이다. 스스로 논리가 이해가 된다면 우선 구현을 취한 뒤에, 문제가 없겠다고 판단이 선 이후에 + 시간이 남는다면 코드 최적화를 고려해볼 수 있겠다.
public class BOJ_21611_마법사상어와블리자드 {
private static int N, M, tdx;
private static int[][] map;
private static int[] temp;
private static int oneTotal, twoTotal, threeTotal;
private static int shark;
private static int[] dy = {0, -1, 1, 0, 0}; // 상하좌우 1,2,3,4 동치
private static int[] dx = {0, 0, 0, -1, 1};
private static final int UP = 1;
private static final int DOWN = 2;
private static final int LEFT = 3;
private static final int RIGHT = 4;
private static Deque<int[]> stack;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
shark = (N+1) / 2;
map = new int[N+1][N+1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
blizzard(d, s, 0, shark, shark);
do {
pull();
} while (bomb());
stretch();
}
sb.append(oneTotal + 2*twoTotal + 3*threeTotal);
br.close();
bw.write(sb.toString());
bw.flush();
bw.close();
}
private static boolean inRange(int y, int x) {
return y >= 1 && y <= N && x >= 1 && x <= N;
}
private static void blizzard(int d, int s, int depth, int y, int x) {
if (depth == s) {
return;
}
int ny = y + dy[d];
int nx = x + dx[d];
if (inRange(ny, nx)) {
// 터뜨림
map[ny][nx] = 0;
blizzard(d, s, depth + 1, ny, nx);
}
}
private static boolean bomb() {
stack = new ArrayDeque<>();
int y = shark;
int x = shark;
int peek = -1;
boolean isBomb = false;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
y += dy[LEFT];
x += dx[LEFT];
if (inRange(y, x)) {
if (peek == map[y][x]) {
stack.push(new int[]{y, x});
} else {
if (stack.size() >= 4) {
isBomb = true;
// 점수 계산
if (peek == 1) {
oneTotal += stack.size();
} else if (peek == 2) {
twoTotal += stack.size();
} else if (peek == 3) {
threeTotal += stack.size();
}
// 파괴
while (!stack.isEmpty()) {
int[] pos = stack.pop();
map[pos[0]][pos[1]] = 0;
}
} else {
// 4연속을 충족하지 못하는 구슬은 pass
stack = new ArrayDeque<>();
}
// 지금 꺼는 넣고 다시 시작
stack.push(new int[]{y, x});
peek = map[y][x];
}
}
}
for (int j = 1; j <= i; j++) {
y += dy[DOWN];
x += dx[DOWN];
if (inRange(y, x)) {
if (peek == map[y][x]) {
stack.push(new int[]{y, x});
} else {
if (stack.size() >= 4) {
isBomb = true;
// 점수 계산
if (peek == 1) {
oneTotal += stack.size();
} else if (peek == 2) {
twoTotal += stack.size();
} else if (peek == 3) {
threeTotal += stack.size();
}
// 파괴
while (!stack.isEmpty()) {
int[] pos = stack.pop();
map[pos[0]][pos[1]] = 0;
}
} else {
// 4연속을 충족하지 못하는 구슬은 pass
stack = new ArrayDeque<>();
}
// 지금 꺼는 넣고 다시 시작
stack.push(new int[]{y, x});
peek = map[y][x];
}
}
}
i++;
for (int j = 1; j <= i; j++) {
y += dy[RIGHT];
x += dx[RIGHT];
if (inRange(y, x)) {
if (peek == map[y][x]) {
stack.push(new int[]{y, x});
} else {
if (stack.size() >= 4) {
isBomb = true;
// 점수 계산
if (peek == 1) {
oneTotal += stack.size();
} else if (peek == 2) {
twoTotal += stack.size();
} else if (peek == 3) {
threeTotal += stack.size();
}
// 파괴
while (!stack.isEmpty()) {
int[] pos = stack.pop();
map[pos[0]][pos[1]] = 0;
}
} else {
// 4연속을 충족하지 못하는 구슬은 pass
stack = new ArrayDeque<>();
}
// 지금 꺼는 넣고 다시 시작
stack.push(new int[]{y, x});
peek = map[y][x];
}
}
}
for (int j = 1; j <= i; j++) {
y += dy[UP];
x += dx[UP];
if (inRange(y, x)) {
if (peek == map[y][x]) {
stack.push(new int[]{y, x});
} else {
if (stack.size() >= 4) {
isBomb = true;
// 점수 계산
if (peek == 1) {
oneTotal += stack.size();
} else if (peek == 2) {
twoTotal += stack.size();
} else if (peek == 3) {
threeTotal += stack.size();
}
// 파괴
while (!stack.isEmpty()) {
int[] pos = stack.pop();
map[pos[0]][pos[1]] = 0;
}
} else {
// 4연속을 충족하지 못하는 구슬은 pass
stack = new ArrayDeque<>();
}
// 지금 꺼는 넣고 다시 시작
stack.push(new int[]{y, x});
peek = map[y][x];
}
}
}
}
return isBomb;
}
private static void pull() {
temp = new int[N * N];
copy();
paste();
}
private static void paste() {
tdx = 0;
int y = shark;
int x = shark;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
y += dy[LEFT];
x += dx[LEFT];
if (inRange(y, x)) {
map[y][x] = temp[tdx++];
}
}
for (int j = 1; j <= i; j++) {
y += dy[DOWN];
x += dx[DOWN];
if (inRange(y, x)) {
map[y][x] = temp[tdx++];
}
}
i++;
for (int j = 1; j <= i; j++) {
y += dy[RIGHT];
x += dx[RIGHT];
if (inRange(y, x)) {
map[y][x] = temp[tdx++];
}
}
for (int j = 1; j <= i; j++) {
y += dy[UP];
x += dx[UP];
if (inRange(y, x)) {
map[y][x] = temp[tdx++];
}
}
}
}
private static void copy() {
tdx = 0;
int y = shark;
int x = shark;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
y += dy[LEFT];
x += dx[LEFT];
if (inRange(y, x) && map[y][x] > 0) {
temp[tdx++] = map[y][x];
}
}
for (int j = 1; j <= i; j++) {
y += dy[DOWN];
x += dx[DOWN];
if (inRange(y, x) && map[y][x] > 0) {
temp[tdx++] = map[y][x];
}
}
i++; // 복사 길이 늘림 for 달팽이탐색
for (int j = 1; j <= i; j++) {
y += dy[RIGHT];
x += dx[RIGHT];
if (inRange(y, x) && map[y][x] > 0) {
temp[tdx++] = map[y][x];
}
}
for (int j = 1; j <= i; j++) {
y += dy[UP];
x += dx[UP];
if (inRange(y, x) && map[y][x] > 0) {
temp[tdx++] = map[y][x];
}
}
}
}
private static void stretch() {
tdx = 0;
temp = new int[N * N];
int peek = -1;
int cnt = 0;
int y = shark;
int x = shark;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
y += dy[LEFT];
x += dx[LEFT];
if (inRange(y, x)) {
if (peek == map[y][x]) {
cnt++;
} else {
if (cnt > 0) {
if (tdx < N * N) {
temp[tdx++] = cnt;
}
if (tdx < N * N) {
temp[tdx++] = peek;
}
}
cnt = 0;
cnt++;
peek = map[y][x];
}
}
}
for (int j = 1; j <= i; j++) {
y += dy[DOWN];
x += dx[DOWN];
if (inRange(y, x)) {
if (peek == map[y][x]) {
cnt++;
} else {
if (cnt > 0) {
if (tdx < N * N) {
temp[tdx++] = cnt;
}
if (tdx < N * N) {
temp[tdx++] = peek;
}
}
cnt = 0;
cnt++;
peek = map[y][x];
}
}
}
i++;
for (int j = 1; j <= i; j++) {
y += dy[RIGHT];
x += dx[RIGHT];
if (inRange(y, x)) {
if (peek == map[y][x]) {
cnt++;
} else {
if (cnt > 0) {
if (tdx < N * N) {
temp[tdx++] = cnt;
}
if (tdx < N * N) {
temp[tdx++] = peek;
}
}
cnt = 0;
cnt++;
peek = map[y][x];
}
}
}
for (int j = 1; j <= i; j++) {
y += dy[UP];
x += dx[UP];
if (inRange(y, x)) {
if (peek == map[y][x]) {
cnt++;
} else {
if (cnt > 0) {
if (tdx < N * N) {
temp[tdx++] = cnt;
}
if (tdx < N * N) {
temp[tdx++] = peek;
}
}
cnt = 0;
cnt++;
peek = map[y][x];
}
}
}
}
paste();
}
}
'workspace > 알고리즘' 카테고리의 다른 글
| [Java/구현] 백준 18808. 스티커 붙이기 (0) | 2024.03.10 |
|---|---|
| [Java/Union-find] 백준 1043. 거짓말 (0) | 2024.03.08 |
| [Java/Greedy] 백준 1911. 흙길 보수하기 (1) | 2024.03.06 |
| [자바/Simulation] 백준 23796. 2,147,483,648 게임 (1) | 2024.03.05 |
| [자바/Parametric-Search] 백준 2110. 공유기 설치 (1) | 2024.02.25 |
Comments