문제 URL : https://www.acmicpc.net/problem/2933
2933번: 미네랄
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄
www.acmicpc.net
문제접근법 :
문제 설명이 조금애매한부분이 있던데데
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
그 막대를 던지면 그행에 관한 미네랄 전부가 파괴되는줄알았는데 미네랄 한개만 그렇게되면 미네랄 뭉치들이(클러스터) 절대로 한개만 떨어질수가 없더군요
그러니 미네랄은 왼쪽에서 던지거나 오른쪽에서 던질때 마다 한개만 파괴되고 공중에 떠있는 미네랄뭉치(클러스터)를 찾아 바닥으로 떨어 뜨립니다.
하지만 중요한건 바닥에 있는 미네랄 뭉치(클러스터)와 공중에 떠있는 미네랄뭉치(클러스터)와 구분을 하기위해
바닥에 있는 미네랄 뭉치들을 bfs로 연결하여 공중에있는 클러스터를 찾아 바닥에 떨어뜨리는 시뮬레이션을 구현하면 됩니다.
시뮬레이션 문제인데 자바를 연습중이라 자바로 풀려니까 라이브러리 관련을 너무 못쓰니까 2시간정도를 못풀었는데
c++로 다시 짜니까 금방 풀려서 참 언어마다 연습이 중요한걸 깨달았네요
c++과 ,java 소스코드를 보여드리겠습니다. 알고리즘 방법은 완전히 동일하지만 라이브러리를 사용하기위한 코드들은 다를수밖에 없네요
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
char board[100][100];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m;
vector<int> v;
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
int t;
cin >> t;
v.resize(t);
for (int i = 0; i < t; i++)
cin >> v[i];
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
pair<int,int> Throw(int h, int cnt) {
int y = n - h;
int x = cnt % 2 == 0 ? 0 : m - 1; //왼쪽에서 던질지 오른쪽에서 던질지
while (isrange(y, x)&&board[y][x]=='.') {
x += cnt % 2 == 0 ? 1 : -1; //왼쪽에서 던지면 더해주고 오른쪽에서 던지면 빼줌
}
return { y,x };
}
//y가 큰값을기준으로 내림차순
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first > b.first;
}
void bfs(pair<int,int> p) {
int check[100][100] = { 0 };
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
if (board[n - 1][i] == 'x') {
q.push({ n - 1,i });
check[n - 1][i] = 1;
}
}
//바닥에있는 클러스터 연결
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && check[ny][nx] == 0 && board[ny][nx] == 'x') {
q.push({ ny,nx });
check[ny][nx] = 1;
}
}
}
//공중에있는 클러스터
vector<pair<int,int>> dv;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'x' && check[i][j] == 0) {
dv.push_back({ i,j });
}
}
}
//바닥에 떨어뜨리기위해 y큰값을 기준으로 정렬
sort(dv.begin(), dv.end(),cmp);
vector<pair<int, int>> dv2 = dv;
while (!dv.empty()) {
vector<pair<int, int>> temp;
bool flag = false;
//전부 한칸씩 떨어뜨려봄 바닥에있는 클러스터혹은 바닥에 닿을때까지
for (int i = 0; i < dv.size(); i++) {
int y = dv[i].first + 1;
int x = dv[i].second;
if (!isrange(y, x)) { flag = true; break; }
if (check[y][x]) { flag = true; break; }
temp.push_back({ y,x });
}
if (flag)break;
dv = temp;
}
for (auto t : dv2)
board[t.first][t.second] = '.';
for (auto t : dv)
board[t.first][t.second] = 'x';
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << board[i][j];
}
cout << "\n";
}
}
void solve() {
for (int i = 0; i < v.size(); i++) {
pair<int, int> p = Throw(v[i], i);
if (!isrange(p.first, p.second))continue;
board[p.first][p.second] = '.';
bfs(p);
}
print();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
|
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
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static Integer n, m;
public static char board[][];
public static Integer bars[];
public static Integer dy[] = { -1, 0, 1, 0 };
public static Integer dx[] = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new char[n][m];
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < m; j++) {
board[i][j] = s.charAt(j);
}
}
int t = Integer.parseInt(br.readLine());
bars = new Integer[t];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < t; i++) {
bars[i] = Integer.parseInt(st.nextToken());
}
solve();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
bw.write(board[i][j]);
}
bw.write("\n");
}
bw.close();
br.close();
}
public static void bfs(Pair p) {
int check[][] = new int[n][m];
Queue<Pair> q = new LinkedList<Pair>();
for (int i = 0; i < m; i++) {
if (board[n - 1][i] == 'x') {
q.add(new Pair(n - 1, i));
check[n - 1][i] = 1;
}
}
while (!q.isEmpty()) {
Pair cur = q.poll();
for (int i = 0; i < 4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if (isrange(ny, nx)) {
if (check[ny][nx] == 0 && board[ny][nx] == 'x') {
q.add(new Pair(ny, nx));
check[ny][nx] = 1;
}
}
}
}
List<Pair> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'x' && check[i][j] == 0)
list.add(new Pair(i, j));
}
}
Collections.sort(list);
List<Pair> list2 = new ArrayList<>(list);
while (list.size() > 0) {
List<Pair> temp = new ArrayList<>();
boolean flag = false;
for (Pair c : list) {
int y = c.y + 1;
int x = c.x;
if (!isrange(y, x)) {
flag = true;
break;
}
if (check[y][x] == 1) {
flag = true;
break;
}
temp.add(new Pair(y, x));
}
if (flag)
break;
list = temp;
}
for (Pair c : list2)
board[c.y][c.x] = '.';
for (Pair c : list)
board[c.y][c.x] = 'x';
}
public static void solve() {
for (int i = 0; i < bars.length; i++) {
Pair p = Throw(bars[i], i);
if (!isrange(p.y, p.x))
continue;
board[p.y][p.x] = '.';
bfs(p);
}
}
public static boolean isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
public static Pair Throw(int h, int cnt) {
int y = n - h;
int x = cnt % 2 == 0 ? 0 : m - 1;
while (isrange(y, x)) {
if (board[y][x] == 'x')
break;
x += cnt % 2 == 0 ? 1 : -1;
}
return new Pair(y, x);
}
}
class Pair implements Comparable<Pair> {
public Integer y, x;
public Pair(Integer y, Integer x) {
this.y = y;
this.x = x;
}
public Pair() {
}
@Override
public int compareTo(Pair o) {
if (this.y > o.y)
return -1;
return 1;
}
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 3197 백조의 호수 (0) | 2021.12.11 |
|---|---|
| 백준 1726 로봇 (0) | 2021.12.11 |
| 백준 1244 스위치 켜고 끄기 (0) | 2021.11.25 |
| 백준 18310 안테나 (0) | 2021.11.25 |
| 백준 13417 카드 문자열 (0) | 2021.11.25 |
