미네랄 2
https://www.acmicpc.net/problem/18500
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 2109 | 713 | 549 | 34.355% |
문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다.
두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유 인지를 결정하기로 했다.
싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다.
각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다.
막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다.
새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다.
떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 계속해서 떨어진다.
클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다.
모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, ‘.’는 빈 칸, ‘x’는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다.
모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.
첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.
클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
(2933번 문제와 차이)
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
예제 입력 1
5 6 ...... ..xx.. ..x... ..xx.. .xxxx. 1 3
예제 출력 1
...... ...... ..xx.. ..xx.. .xxxx.
예제 입력 2
8 8 ........ ........ ...x.xx. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. 5 6 6 4 3 1
예제 출력 2
........ ........ ........ ........ .....x.. ..xxxx.. ..xxx.x. ..xxxxx.
예제 입력 3
7 6 ...... ...... xx.... .xx... ..xx.. ...xx. ....x. 2 6 4
예제 출력 3
...... ...... ...... ...... ..xx.. xx.xx. .x..x.
예제 입력 A
13 100 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ..................................................x................................................x ..................................................x................................................x ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. ..................................................x................................................. 11 1 1 1 1 1 1 1 1 1 1 1
예제 출력 A
.................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ..................................................x................................................x ...................................................................................................x
예제 입력 B
9 8 ........ ...xxx.. .xxx.... .x.x.xxx .x.x...x .x.xxx.x .x.....x .x.....x .xxx...x 1 7
예제 출력 B
........ ........ ...xxx.. .xxx.xxx .x.x...x .x.x...x .x.xxx.x .x.....x .xxx...x
예제 입력 C
4 4 xxxx xx.x x..x ...x 1 3
예제 출력 C
xxxx .x.x ...x x..x
예제 입력 D
7 5 ..... .xxx. .x... xx.xx x...x x...x x...x 1 4
예제 출력 D
..... ..... .xxx. .x.xx xx..x x...x x...x
예제 입력 E
2 2 .. .x 1 2
예제 출력 E
.. .x
예제 입력 F
5 5 xxxxx x.... xxxxx x.... x.... 10 1 2 3 4 5 1 2 3 4 5
예제 출력 F
..... ..... ..... .xxxx xxxx.
예제 입력 G
10 10 xxxxxxxxxx ....x..... ...xxx.... .....x.... ....xx.... .....x.... xxxxxx.... ..x....... .xxxx..... ...xxxxxxx 10 9 8 7 6 5 4 3 2 1 1
예제 출력 G
.......... .......... .......... .......... .......... .......... xxxxxxxxxx ....xx.... xxxxxx.... .xxxxxxxx.
예제 입력 H
4 4 ...x ..xx .xxx xxxx 10 1 2 3 4 1 2 3 4 3 4
예제 출력 H
.... .... .xxx ..xx
예제 입력 I
10 20 ..xxxxxxxxxxxxxxx... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..xxxxxx........x... ................x... x...............x... 2 1 7
예제 출력 I
.................... ..xxxxxxxxxxxxxxx... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..x.............x... ..xxxxxx........x... ................x...
예제 입력 J
9 8 ........ .xxxx... .x...... .x.xxxx. .x....x. .x....x. .xxxx.x. ....xxx. ......x. 1 2
예제 출력 J
........ ........ .xxxx... .x.xxxx. .x....x. .x....x. .x....x. .xxxxxx. ......x.
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Croatian Regional Competition in Informatics 2009 5번
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Regional Competition – Juniors 4번
- 데이터를 추가한 사람: heize
알고리즘 분류
통과된 코드
나는 2933번을 해결할 때 공중에 있는 미네랄 리스트의 하단부를 전부 확인하는 방법으로 구현해서 다른 것이 없다.
골드 2 문제를 해결하니 골드 1을 같이 주네?? 개꿀
#include <iostream>
#include <list>
#include <queue>
using namespace std;
// RC의 범위 최대값
constexpr int MAX = 101;
// 기본 맵
char map[MAX][MAX];
// 방문처리
bool mapCheck[MAX][MAX];
// BFS 사용할 Q
queue<pair<int, int>> myQ;
pair<int, int> tempP;
// R 행, C 열, N 막대기를 던진 횟수
int R, C, N;
int dx, dy, dis;
int temp = 0;
// 탐색하는 방향 설정 => 상, 하 ,좌 ,우
int dxdy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
list<int> myList;
list<int>::iterator it;
list<pair<int, int>> cList;
list<pair<int, int>>::iterator cit;
// true = left, false = right
bool check = false, leftRight = false;
void BFS(int x, int y)
{
myQ.push(make_pair(x, y));
while (!myQ.empty()) {
tempP = myQ.front();
myQ.pop();
for (int i = 0; i < 4; i++) {
dy = tempP.second + dxdy[i][1];
dx = tempP.first + dxdy[i][0];
// 문제의 범위를 벗어나는 경우 => 넘어간다.
if (dx <= 0 || dy <= 0 || dy > C || dx > R) continue;
// 방문 처리가 되었거나 빈공간 => 넘어간다.
if (mapCheck[dx][dy] == true || map[dx][dy] == '.') continue;
mapCheck[dx][dy] = true;
myQ.push(make_pair(dx, dy));
}
}
}
void CheckFloor() // 바닥을 체크합니다.
{
for (int y = 1; y <= C; y++) {
// 바닥에 클러스터가 발견되고 방문처리가 되지 않았다면
if (map[1][y] == 'x' && mapCheck[1][y] == false) {
BFS(1, y); // BFS로 마킹
}
}
}
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
// 처음 맵을 초기화 해준다.
for (int x = 1; x < MAX; x++) {
for (int y = 1; y < MAX; y++) {
map[x][y] = '.';
}
}
cin >> R >> C;
// 미네랄의 위치를 설정 (아래서 부터 시작)
for (int x = R; x >= 1; x--) {
for (int y = 1; y <= C; y++) {
cin >> map[x][y];
}
}
cin >> N;
/// 던진 횟수와 높이를 설정
while (N > 0) {
cin >> temp;
myList.push_back(temp);
N--;
}
// 던진 막대기 리스트를 순회합니다.
for (it = myList.begin(); it != myList.end(); it++) {
check = false; // 미네랄 부셔짐 체크 해제
cList.clear(); // 공중의 미네랄 리스트 초기화
// 해당 위치에 미네랄이 있는지 검색합니다.
if (leftRight) { // 좌측 검색
for (int y = C; y >= 1; y--) {
// 만약 미네랄이 있다면
if (map[*it][y] == 'x') {
// 해당 미네랄을 빈 공간으로 만든다.
map[*it][y] = '.';
// 바닥과 연결된 모든 클러스터를 방문처리
CheckFloor();
check = true;
break;
}
}
leftRight = !leftRight;
}
else { // 우측 검색
for (int y = 1; y <= C; y++) {
// 만약 미네랄이 있다면
if (map[*it][y] == 'x') {
// 해당 미네랄을 빈 공간으로 만든다.
map[*it][y] = '.';
// 바닥과 연결된 모든 클러스터를 방문처리
CheckFloor();
check = true;
break;
}
}
leftRight = !leftRight;
}
if (check) { // 미네랄이 부셔졌다면
// 공중에 있는 클러스트들을 리스트에 담는다.
for (int x = R; x >= 1; x--) {
for (int y = C; y >= 1; y--) {
if (map[x][y] == 'x' && mapCheck[x][y] == false) {
cList.push_back(make_pair(x, y));
}
}
}
// 공중에 미네랄이 바닥과 연결될때까지 반복
dis = 1;
bool floor = true;
while (floor) {
if (cList.size() == 0) break;
for (cit = cList.begin(); cit != cList.end(); cit++) {
tempP.first = cit->first;
tempP.second = cit->second;
if (mapCheck[tempP.first - (dis + 1)][tempP.second] == true || tempP.first - (dis + 1) == 0) {
floor = false;
break;
}
}
dis++;
}
if (!floor) {
for (cit = cList.begin(); cit != cList.end(); cit++) {
tempP.first = cit->first;
tempP.second = cit->second;
map[tempP.first][tempP.second] = '.';
}
for (cit = cList.begin(); cit != cList.end(); cit++) {
tempP.first = cit->first;
tempP.second = cit->second;
map[tempP.first - (dis - 1)][tempP.second] = 'x';
}
}
// 방문 처리를 초기화
for (int x = R; x >= 1; x--) {
for (int y = 1; y <= C; y++) {
mapCheck[x][y] = false;
}
}
}
}
for (int x = R; x >= 1; x--) {
for (int y = 1; y <= C; y++) {
cout << map[x][y];
}
if (x == 1) break;
cout << "\n";
}
return 0;
}
![백준 27866번 (문자와 문자열, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)
![백준 2559번 (수열, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)