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

글쓴이 / / BaekjoonOnlineJudge, C++/CPP

미네랄

https://www.acmicpc.net/problem/2933

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초128 MB107522935191725.250%

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다.

두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유 인지를 결정하기로 했다.

싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다.

각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다.

막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다.

새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다.

떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 계속해서 떨어진다.

클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다.

모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, ‘.’는 빈 칸, ‘x’는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다.

모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.

첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.

클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

출력

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

예제 입력 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

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

예제 출력 B

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

예제 입력 C

2 2
..
.x
1
2

예제 출력 C

..
.x

예제 입력 D

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

예제 출력 D

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

예제 입력 E

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

예제 출력 E

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

출처

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: jh05013
  • 어색한 표현을 찾은 사람: porrshe

알고리즘 분류

첫째 줄에 동굴의 크기 R과 C (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, ‘.’는 빈 칸, ‘x’는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.

클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

예제 1

예제 2

예제 3

이번에도 문제를 이해하는 것이 오래 걸렸다.. 일단 글을 읽으면 머리 속에서 잘 정리가 되지 않는다.

한 3~4 번을 다시 글을 읽은 후에야 어느 정도 이해를 하는 듯….

일단 동굴을 코드로 구현해보자

#include<iostream>
#include<list>

using namespace std;

// RC의 범위 최대값
constexpr int MAX = 101;

// 기본 맵
char map[MAX][MAX];

// R 행, C 열, N 막대기를 던진 횟수
int R, C, N;

int temp = 0;


list<int> myList;
list<int>::iterator it;

bool debug = true;

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

	if (debug) {
		for (int x = R; x >= 1; x--) {
			for (int y = 1; y <= C; y++) {
				cout << map[x][y] << " ";
			}
			cout << "\n";
		}
		cout << "\n던진 막대기 높이 리스트\n";
		for (it = myList.begin(); it != myList.end(); it++) cout << *it << " ";
	}
	return 0;
}

다행히 생각대로 잘나온다.

이제 막대기를 던져서 해당 위치의 미네랄을 파괴하는 것까지 구현

#include<iostream>
#include<list>

using namespace std;

// RC의 범위 최대값
constexpr int MAX = 101;

// 기본 맵
char map[MAX][MAX];

// R 행, C 열, N 막대기를 던진 횟수
int R, C, N;

int temp = 0;


list<int> myList;
list<int>::iterator it;

bool debug = true;

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++) {
		// 해당 위치에 미네랄이 있는지 검색합니다.
		// 일단은 좌->우 검색
		for (int x = 1; x <= C; x++) {
			// 만약 미네랄이 있다면
			if (map[*it][x] == 'x') {
				cout << "\n찾음\n";
				// 해당 미네랄을 빈 공간
				map[*it][x] = '.';
				break;
			}
		}
	}




	if (debug) {
		for (int x = R; x >= 1; x--) {
			for (int y = 1; y <= C; y++) {
				cout << map[x][y] << " ";
			}
			cout << "\n";
		}
		cout << "\n던진 막대기 높이 리스트\n";
		for (it = myList.begin(); it != myList.end(); it++) cout << *it << " ";
	}
	return 0;
}

이제 좌/우에서 던지는 것을 구현해야 한다.

2가지 경우 좌/우 이므로 bool 값으로 체크해서 막대기를 던지는 것을 구현하였다.

#include<iostream>
#include<list>

using namespace std;

// RC의 범위 최대값
constexpr int MAX = 101;

// 기본 맵
char map[MAX][MAX];

// R 행, C 열, N 막대기를 던진 횟수
int R, C, N;

int temp = 0;


list<int> myList;
list<int>::iterator it;

// true = left, false = right
bool leftRight = true;

bool debug = true;

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++) {
		
		// 해당 위치에 미네랄이 있는지 검색합니다.
		// 일단은 좌->우 검색
		if (leftRight) { // 좌측 검색
			for (int y = 1; y <= C; y++) {
				// 만약 미네랄이 있다면
				if (map[*it][y] == 'x') {
					cout << "\n찾음\n";
					// 해당 미네랄을 빈 공간
					map[*it][y] = '.';
					break;
				}
			}
			leftRight = !leftRight;
		}
		else { // 우측 검색
			for (int y = C; y >= 1; y--) {
				// 만약 미네랄이 있다면
				if (map[*it][y] == 'x') {
					cout << "\n찾음\n";
					// 해당 미네랄을 빈 공간
					map[*it][y] = '.';
					break;
				}
			}
			leftRight = !leftRight;
		}

	}

	if (debug) {
		for (int x = R; x >= 1; x--) {
			for (int y = 1; y <= C; y++) {
				cout << map[x][y] << " ";
			}
			cout << "\n";
		}
		cout << "\n던진 막대기 높이 리스트\n";
		for (it = myList.begin(); it != myList.end(); it++) cout << *it << " ";
	}
	return 0;
}

생각대로 미네랄이 잘 파괴가 되는 것 같다.

이제 미네랄이 파괴 되었을 경우 여기서 말하는 클러스터(상하좌우가 연결된 미네랄 덩이)가

공중에 떠있지 못하게 하기만 하면 끝일 것 같은데…. 방법이 문제다.

미네랄이 파괴되면 바닥과 연결된 미네랄을 모두 마킹해 주었다. 

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

int temp = 0;

// 탐색하는 방향 설정 =>  상, 하 ,좌 ,우
int dxdy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };


list<int> myList;
list<int>::iterator it;

// true = left, false = right
bool check = false, leftRight = true;

bool debug = true;

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 || dx > C || dy > 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++) {
		
		// 해당 위치에 미네랄이 있는지 검색합니다.
		// 일단은 좌->우 검색
		if (leftRight) { // 좌측 검색
			for (int y = 1; y <= C; y++) {
				// 만약 미네랄이 있다면
				if (map[*it][y] == 'x') {
					// 해당 미네랄을 빈 공간으로 만든다.
					map[*it][y] = '.';
					// 바닥과 연결된 모든 클러스터를 방문처리
					CheckFloor();
					check = true;
					break;

				}
			}

			leftRight = !leftRight;
		}
		else { // 우측 검색
			for (int y = C; y >= 1; 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 = 1; y <= C; y++) {
					mapCheck[x][y] = false;
				}
			}
			check = false;
		}

	}

	if (debug) {

		for (int x = R; x >= 1; x--) {
			for (int y = 1; y <= C; y++) {
				cout << map[x][y] << " ";
			}
			cout << "\n";
		}
		cout << "\n던진 막대기 높이 리스트\n";
		for (it = myList.begin(); it != myList.end(); it++) cout << *it << " ";
	}

	return 0;

}

이제 공중에 있는 클러스터들의 좌표들을 저장하는 리스트를 만들고 확인

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

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 = true;

bool debug = true;

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 || dx > C || dy > 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++) {
		cList.clear();
		// 해당 위치에 미네랄이 있는지 검색합니다.
		// 일단은 좌->우 검색
		if (leftRight) { // 좌측 검색
			for (int y = 1; y <= C; y++) {
				// 만약 미네랄이 있다면
				if (map[*it][y] == 'x') {
					// 해당 미네랄을 빈 공간으로 만든다.
					map[*it][y] = '.';
					// 바닥과 연결된 모든 클러스터를 방문처리
					CheckFloor();
					check = true;
					break;

				}
			}

			leftRight = !leftRight;
		}
		else { // 우측 검색
			for (int y = C; y >= 1; 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 = 1; y <= C; y++) {
					if (map[x][y] == 'x' && mapCheck[x][y] == false) {
						cList.push_back(make_pair(x, y));
					}
				}
			}


			// 방문 처리를 초기화 
			for (int x = R; x >= 1; x--) {
				for (int y = 1; y <= C; y++) {
					mapCheck[x][y] = false;
				}
			}
			check = false;
		}

	}

	if (debug) {

		for (int x = R; x >= 1; x--) {
			for (int y = 1; y <= C; y++) {
				cout << map[x][y] << " ";
			}
			cout << "\n";
		}
		cout << "\n던진 막대기 높이 리스트\n";
		for (it = myList.begin(); it != myList.end(); it++) cout << *it << " ";
		cout << "\n떠있는 클러스터 리스트 리스트\n";
		for (cit = cList.begin(); cit != cList.end(); cit++) cout << " x : " << cit->first << " y : " << cit->second << "\n";
	}

	return 0;

}

통과된 코드

미네랄이 파괴되면 바닥과 연결된 미네랄을 방문 처리해준다.

맵 전체에서 방문처리가 되지 않은 미네랄을 리스트에 담아준다

미네랄 리스트를 순회하면서 아래 부분이 방문 처리가 된 곳인지 확인한다. (내려갈 길이를 찾기 위함)

하단부가 방문처리가 되었다면 그 거리 -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;

}

계속 틀린 원인은 바닥과 연결된 클러스터를 찾는 BFS 탐색에서 R과 C의 범위를 바꾸어 탐색

이 부분 하나로 엄청난 시간을 낭비

웃긴 부분은 다른 테스트 케이스는 다 잘돌아감 ㅋㅋ

구현이 조금 빡센 문제…

“백준 2933번 (미네랄, C++, Simulation) / 추가 반례 [BAEKJOON]”에 대한 1개의 생각

  1. 핑백: 백준 18500번 (미네랄 2, C++, Simulation) / 추가 반례 [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

관련 게시물

백준 11723번 (집합, C++, 비트마스킹) [BAEKJOON]

백준 11723번 (집합, C++, 비트마스킹) [BAEKJOON]

BaekjoonOnlineJudge, C++/CPP / 글쓴이 / / , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

백준(BAEKJOON) 11723번 '집합' 문제에 대한 글 입니다. 비트마스킹, 배열, Set을 이용하여 해결하였습니다.…

위로 스크롤