백준 18500번 (미네랄 2, C++, Simulation) / 추가 반례 [BAEKJOON]

문제

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

plaintext

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

예제 출력 1

plaintext

......
......
..xx..
..xx..
.xxxx.

예제 입력 2

plaintext

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

예제 출력 2

plaintext

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

예제 입력 3

plaintext

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4

예제 출력 3

plaintext

......
......
......
......
..xx..
xx.xx.
.x..x.

예제 입력 A

plaintext

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

plaintext

....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
..................................................x................................................x
...................................................................................................x

예제 입력 B

plaintext

9 8
........
...xxx..
.xxx....
.x.x.xxx
.x.x...x
.x.xxx.x
.x.....x
.x.....x
.xxx...x
1
7

예제 출력 B

plaintext

........
........
...xxx..
.xxx.xxx
.x.x...x
.x.x...x
.x.xxx.x
.x.....x
.xxx...x

예제 입력 C

plaintext

4 4
xxxx
xx.x
x..x
...x
1
3

예제 출력 C

plaintext

xxxx
.x.x
...x
x..x

예제 입력 D

plaintext

7 5
.....
.xxx.
.x...
xx.xx
x...x
x...x
x...x
1
4

예제 출력 D

plaintext

.....
.....
.xxx.
.x.xx
xx..x
x...x
x...x

예제 입력 E

plaintext

2 2
..
.x
1
2

예제 출력 E

plaintext

..
.x

예제 입력 F

plaintext

5 5
xxxxx
x....
xxxxx
x....
x....
10 1 2 3 4 5 1 2 3 4 5

예제 출력 F

plaintext

.....
.....
.....
.xxxx
xxxx.

예제 입력 G

plaintext

10 10
xxxxxxxxxx
....x.....
...xxx....
.....x....
....xx....
.....x....
xxxxxx....
..x.......
.xxxx.....
...xxxxxxx
10 9 8 7 6 5 4 3 2 1 1

예제 출력 G

plaintext

..........
..........
..........
..........
..........
..........
xxxxxxxxxx
....xx....
xxxxxx....
.xxxxxxxx.

예제 입력 H

plaintext

4 4
...x
..xx
.xxx
xxxx
10 1 2 3 4 1 2 3 4 3 4

예제 출력 H

plaintext

....
....
.xxx
..xx

예제 입력 I

plaintext

10 20
..xxxxxxxxxxxxxxx...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..xxxxxx........x...
................x...
x...............x...
2
1 7

예제 출력 I

plaintext

....................
..xxxxxxxxxxxxxxx...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..x.............x...
..xxxxxx........x...
................x...

예제 입력 J

plaintext

9 8
........
.xxxx...
.x......
.x.xxxx.
.x....x.
.x....x.
.xxxx.x.
....xxx.
......x.
1
2

예제 출력 J

plaintext

........
........
.xxxx...
.x.xxxx.
.x....x.
.x....x.
.x....x.
.xxxxxx.
......x.

알고리즘 분류

백준 2933번 (미네랄, C++, Simulation) / 추가 반례

출처

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을 같이 주네?? 개꿀

통과된 코드

cpp

#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;

}