글 읽기 - 테스트케이스는 맞지만 틀렸습니다가 뜹니다 ㅠㅠ

bumjun6602 5년 전 0

질문에 있는 테스트케이스들도 돌려봤는데 맞게 나오는거 같은데 채점하면 틀리네요 ㅠㅠ

100*100 테케도 넣어봤습니다.

어디가 잘못되었는지 알수 있을까요?

로직은 다음처럼 짯습니다.

막대기를 던져 맞은칸의 미네랄을 없앤다.
없어진 미네랄 주위의 위/왼쪽/오른쪽을 체크해 공중에 뜨게 됐을 클러스터를 찾는다.
공중에 떠있는 클러스터를 발견시
- 미리 벡터에 넣어놓은 각 클러스터의 좌표를 아래칸에 있는 것이 먼저 나오게 정렬한다
- 떨어지면서 바닥이나 미네랄에 닿을 수 있는 칸만 확인한다
- 밑에 닿은 칸이 없을 경우 밑으로 내리고 닿았으면 리턴

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
int n, m, oper[100], k, dir[4][2] = { {0,-1},{-1,0},{0,1 },{1,0} };
char map[101][101];
int eraseM(int, int);
bool bfs(int, int);
bool isRange(int r, int c) {
	if (r < 1 || r > n || c < 1 || c > m) return false;
	return true;
}

bool compare(pair<int, int> a, pair<int, int> b) {
	return a.first > b.first;
}
int main() {
	cin >> n >> m;

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> map[i][j];
		}
	}
	cin >> k;
	for (int i = 0;i < k;i++) {
		int temp;
		cin >> temp;
		oper[i] = n - temp + 1;
	}

	for (int i = 0;i < k;i++) {
		int c;
		if (i % 2 == 0) {
			c = eraseM(oper[i], 0); //왼쪽에서
		}
		else {
			c = eraseM(oper[i], 1); // 오른쪽에서
		}

		if (c == -1) continue; // 터진 미네랄이 없을 때

		for (int j = 0;j < 3;j++) { //공중에 떠있을 확률이 있는 위,왼쪽,오른쪽 방향 블록 bfs 탐색
			int tempR, tempC;
			tempR = oper[i] + dir[j][0];
			tempC = c + dir[j][1];
			if (isRange(tempR, tempC) == false || map[tempR][tempC] == '.') continue;
			if (bfs(tempR, tempC)) { // 공중에 떠있었다면 두개 이상 떠있지 않으므로 break
				break;
			}
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cout << map[i][j];
		}cout << "\n";
	}
}
// 부딪힌 미네랄 지우고 위치 반환
int eraseM(int h, int direction) {
	if (direction == 0) { //왼쪽에서 던짐
		for (int i = 1;i <= m;i++) {
			if (map[h][i] == 'x') {
				map[h][i] = '.';
				return i; // 터진 미네랄의 열 리턴
			}
		}
	}
	else { // 오른쪽에서 던짐
		for (int i = m;i >= 1;i--) {
			if (map[h][i] == 'x') {
				map[h][i] = '.';
				return i; // 터진 미네랄의 열 리턴
			}
		}
	}
	return -1; // 터진게 없으면 -1 리턴
}

//클러스터가 떠있는지 체크, 떠있다면 밑으로 내리기
bool bfs(int startR, int startC) {
	vector<pair<int, int>> point;
	queue<pair<int, int>> q;
	bool isVisit[101][101] = { false, };
	q.push({ startR,startC });
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		point.push_back({ r,c }); // 떠있는 블록일 경우를 감안해 벡터에 담아놓음
		for (int i = 0;i < 4;i++) {
			int tempR = r + dir[i][0];
			int tempC = c + dir[i][1];
			if (isRange(tempR, tempC) == false || map[tempR][tempC] == '.' || isVisit[tempR][tempC]) continue;
			q.push({ tempR,tempC });
			isVisit[tempR][tempC] = true;
		}
	}
	for (int i = 0;i < point.size();i++) { // 클러스터가 한칸이라도 바닥에 붙어있으면 false 리턴
		int tempR = point[i].first;
		int tempC = point[i].second;
		if (tempR == n) {
			return false;
		}
	}

	//클러스터 한칸씩 내리기
	bool check[101][101] = { false, }, chkBlock[10000];
	sort(point.begin(), point.end(), compare); // 밑에 있는 블록부터 내려주기 위해 클러스터 정렬
	for (int i = 0;i < point.size();i++) {
		check[point[i].first][point[i].second] = true;
	}
	for (int i = 0;i < point.size();i++) {
		if (check[point[i].first + 1][point[i].second] == false) chkBlock[i] = true; // 밑을 보면서 내려가야 하는 블록만 체크
	}
	while (1) { //밑에 닿을때 까지 반복
		for (int i = 0;i < point.size();i++) {
			int tempR = point[i].first;
			int tempC = point[i].second;
			if (chkBlock[i] == true && (map[tempR + 1][tempC] == 'x' || tempR + 1 > n)) { //바로 밑이 미네랄이거나 바닥인경우 내리기종료
				return true;
			}
		}
		//안 닿고 아직 떠있음
		for (int i = 0;i < point.size();i++) { //클러스터 한칸씩 내림
			map[point[i].first][point[i].second] = '.';
			map[point[i].first + 1][point[i].second] = 'x';
			point[i].first++;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트케이스는 맞지만 틀렸습니다가 뜹니다 ㅠㅠ

bumjun6602 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말