글 읽기 - c++ bfs 81%에서 컷당합니다. (주석 많이 있음)

dkxm99 3년 전 0

어떤 반례가 있길래 왜 안되는지 궁금합니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX (100 + 5)

using namespace std;

int map[MAX][MAX]; //전체 맵
vector<int>v; //맵에 있는 모든 숫자 저장
int drown[MAX * MAX]; // 침몰시킬 숫자가 저장되는 배열
int result[MAX * MAX]; // 최종결과 출력
bool visited[MAX][MAX];
int dx[4] = { 1 ,-1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int n, checkMax;

void bfs(int b, int a, int c) {
	queue<pair<int, int>>q;
	visited[b][a] = true;
	q.push(make_pair(b, a));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (map[ny][nx] > drown[c] && !visited[ny][nx]) { // 예제기준 2부터 9까지 bfs 실행
				visited[ny][nx] = true;
				q.push(make_pair(ny, nx));
			}		
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			v.push_back(map[i][j]); //맵에 있는 모든 숫자를 벡터에 저장
		}
	}
	sort(v.begin(), v.end()); //벡터를 크기순으로 정렬
	v.erase(unique(v.begin(), v.end()), v.end()); //중복되는 수 제거
	for (int i = 0; i < v.size(); i++) {         //예제기준 2,3,4,5,6,7,8,9의 숫자가 중복없이 저장됨
		drown[i] = v[i]; //drown에는 침몰시킬 수 있는 모든 숫자가 저장됨
	}	    //즉 기본 예제같은 경우에는 숫자가 2부터 9까지만 있으므로 drown에는 2부터 9까지의 숫자가 저장됨
	for (int k = 0; k < v.size(); k++) { //벡터의 사이즈만큼 실행, 예제 기준 벡터의 크기는 8이됨
		int cnt = 0;					
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] > drown[k] && !visited[i][j]) {
					cnt++; //모든 구역 계산
					result[k] = cnt;
					bfs(i, j, k);
				}
			}
		}
	}
	sort(result + 0, result + v.size()); //안전영역의 최대 개수를 출력하기 위에 정렬해줌
	cout << result[v.size() - 1]; //제일 큰 수 출력
	return 0;
}

dkxm99 3년 전 6

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

해당 경우를 고려하지 않아서 틀리는거였습니다.

답은 1이지만 제 경우는 0이 나오더군요.

50번째 줄의

drown[i] = v[i]; 이 부분을

drown[i+1] = v[i] 를 해줌으로서 drown의 0번째 칸에는 무조건 0이 들어가 섬이 하나도 침몰하지 않았을 경우를 추가해주었습니다.

rmsghdk 3년 전 0

마침 81% 에서 똑같은 문제로 실패하고 있었는데 감사합니다!

저는 위 코드 기준으로 보면 drown 의 len 가 1인 경우면 1을 출력해주고 종료하고

아니라면 BFS 를 실행한다는 식으로 해결했는데... 그렇게 해결할수도 있겠네요.

많은 도움이 됐습니다!

dkxm99 3년 전 0

도움이 되셨다니 다행입니다!

sangmins23 2년 전 0

출력에 사용할 변수를 1로 초기화 하면 어떤 케이스가 들어와도 통과가 됩니다.

seonghwan7694 1년 전 0

감사합니다. 덕분에 5초만에 수정하고 초록색을 띄웠네요... ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ 기분조아

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

문제

문제

출처

ICPC

c++ bfs 81%에서 컷당합니다. (주석 많이 있음)

dkxm99 3년 전 0

dkxm99 3년 전 6

rmsghdk 3년 전 0

dkxm99 3년 전 0

sangmins23 2년 전 0

seonghwan7694 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말