문제풀이/백준
[백준]18500: 미네랄 2 - JAVA
빈둥벤둥
2021. 8. 25. 16:29
[백준]18500: 미네랄 2
18500번: 미네랄 2
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄
www.acmicpc.net
풀이
🪑 구현문제이다. 빡구현 문제. 풀이 방법이 정말 다향할 수 있는 문제라고 생각한다. 내 코드는 메모리 측면이나 코드 라인 측면이나 시간복잡도 측면에서 효율적이지 않은 코드이다. 하지만 다르게 최적화 할 방법이 떠오르지 않는다..ㅠㅠ
📝 문제를 정리해 보자!
- 왼쪽, 오른쪽에서 번갈아 막대기를 던진다.
- 막대기가 날아가다가 미네랄을 만나면 미네랄이 파괴되고 막대의 이동은 멈춘다.
- 미네랄이 파괴된 다음 공중에 뜨게 된 클러스터는 중력에 의해 바닥으로 떨어진다.
- 왼쪽부터 시작한다.
🔧 문제를 순서대로 풀어보자! 구현 문제는 순서대로 차근차근 푸는 것이 중요하다.
- 막대기를 던진다.
- 막대기가 미네랄을 만나면 해당 미네랄을 파괴한다.
- 클러스터가 새로 생성되었는지 확인한다.
- 새로 생성된 경우 분리된 클러스터라면 중력에 의해 떨어진다.
- 분리가 되지 않는 경우 다시 1번부터 던지기를 시작한다.
🔹 막대기를 던진다.
- 홀수번째 일때는 왼쪽에서, 짝수번째 일때는 오른쪽에서 던진다.
🔹 막대기가 미네랄을 만나면 해당 미네랄을 파괴한다.
- 이 부분은 DFS로 구현하였다.
- 한 방향으로 계속 탐색하다가 미네랄을 만나면 해당 미네랄을 파괴하고 탐색을 종료한다.
🔹 클러스터가 새로 생성되었는지 확인하고, 새로 생성된 경우 분리된 클러스터인지도 함께 확인한다.
- 풀이 순서의 3+4 조건을 한번에 체크해 주었다. BFS탐색 한번 만에 결과를 반환해 주고 싶었기 때문이다.
- 분리된 클러스터를 BFS탐색을 하며 확인해 주었고, 분리된 경우 땅으로 떨어질 수 있는 클러스터인지도 함께 확인해 주었다.
- 땅에 떨어질 수 있는지 여부는 해당 클러스터 내부에 바닥과 맞닿아있는 클러스터가 있는지 여부로 확인해 주었다.
- 땅에 떨어질 수 있는 클러스터가 있다면 true라는 플래그와 해당 클러스터에 포함된 모든 노드를 저장해 주도록 하였다.
- 이때 두 개 이상의 클러스터가 동시에 떨어지는 경우는 없으므로 한 번 땅에 떨어질 수 있는 클러스터를 찾았다면 더 이상 탐색을 진행하지 않아도 된다.
🔹 분리된 클러스터를 떨어뜨린다.
- 클러스터를 떨어뜨리면서 아래로 떨어질 수 있는 상태인지(아래 미네랄이 없거나 바닥을 벗어나지 않는지)확인하는데 오류를 없애기 위해 x좌표가 큰 순서대로 정렬시켜 주었다.
- 노드를 하나씩 확인하며 클러스터를 한 칸씩 내려주었고, 중간에 떨어질 수 없는 상태라면 지금까지의 변경된 상태를 무시해줘야 하므로 현재 board의 상태를 copy해서 copy된 board를 사용하였다.
- 모든 연산이 끝난 후 다음 던지기를 시작하며 클러스터가 분리되지 않은 경우에는 바로 다음 던지기를 시작한다.
코드
|
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
|
//18500: 미네랄 2
import java.io.*;
import java.util.*;
public class Main {
static final int LEFT = 1;
static final int RIGHT = -1;
static int r, c;
static char[][] board;
public static void main(String[] args) throws IOException {
//입력
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = bf.readLine();
StringTokenizer st = new StringTokenizer(str);
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
board = new char[r][c];
for(int i = 0; i < r; i++) {
str = bf.readLine();
for(int j = 0; j < c; j++) {
board[i][j] = str.charAt(j);
}
}
int n = Integer.parseInt(bf.readLine());
int[] turn = new int[n];
str = bf.readLine();
st = new StringTokenizer(str);
for(int i = 0; i < n; i++) {
turn[i] = Integer.parseInt(st.nextToken());
}
//입력 끝
fight(turn);
print_board();
}
public static void print_board() {
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
public static void fight(int[] turn) {
for(int i = 0; i < turn.length; i++) {
//막대기 던지기
if(i % 2 == 0) dfs(0, LEFT, r - turn[i]);
else dfs(c - 1, RIGHT, r - turn[i]);
//새로 생성된 클러스터가 있는지 -> 있다면 떨어져야 하는지 확인
check_and_fall();
}
}
public static void dfs(int idx, int dir, int height) {
if(idx >= c || idx < 0) return;
if(board[height][idx] == 'x') {
board[height][idx] = '.';
return;
}
dfs(idx + dir, dir, height);
}
public static void check_and_fall() {
boolean[][] visited = new boolean[r][c];
ArrayList<Node> fall_node = new ArrayList<>();
for(int i = 0; i < r; i++) {
if(!fall_node.isEmpty()) break; //두개 이상 클러스터가 동시에 떨어지는 경우 없으므로 떨어질 수 있는 클러스터 하나 찾으면 탐색 끝냄.
for(int j = 0; j < c; j++) {
if(!visited[i][j] && board[i][j] == 'x') {
Object[] result = bfs_andFallCheck(visited, i, j);
if((boolean) result[0]) fall_node = (ArrayList<Main.Node>) result[1];
}
}
}
if(fall_node.isEmpty()) return;
Collections.sort(fall_node, (o1, o2) -> o2.x - o1.x);
fall_cluster(fall_node);
}
public static Object[] bfs_andFallCheck(boolean[][] visited, int x, int y) {
int[] dx = {0, 1, 0 ,-1};
int[] dy = {1, 0, -1, 0};
Queue<Node> q = new LinkedList<>();
ArrayList<Node> list = new ArrayList<>();
visited[x][y] = true;
q.offer(new Node(x, y));
list.add(new Node(x, y));
boolean isFall = true;
while(!q.isEmpty()) {
Node current = q.poll();
for(int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if(board[nx][ny] != 'x' || visited[nx][ny]) continue;
visited[nx][ny] = true;
list.add(new Node(nx, ny));
q.offer(new Node(nx, ny));
if(nx == r - 1) isFall = false;
}
}
return new Object[] {isFall, list};
}
public static void fall_cluster(ArrayList<Node> list) {
while(true) {
char[][] copy = copy_board(board);
boolean check = true;
for(Node current : list) {
if(current.x + 1 >= r) {
check = false;
break;
}
if(copy[current.x + 1][current.y] == 'x') {
check = false;
break;
}
copy[current.x++][current.y] = '.';
copy[current.x][current.y] = 'x';
}
if(!check) break;
board = copy_board(copy);
}
}
public static char[][] copy_board(char[][] board) {
char[][] copy = new char[r][c];
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
copy[i][j] = board[i][j];
}
}
return copy;
}
public static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
|
cs |