글 읽기 - bfs 하면서 'G' 값을 바꿨는데 틀렸다고 뜹니다

aegamro 4년 전 0

색약이 아닌 사람이 봤을 때와 색약인 사람이 봤을 때의 BFS 함수를 각각 만들어 처리하는 방법으로 접근하려 했습니다.

색약인 사람이 봤을 때의 BFS 함수 내에서 'G'인 경우 'R'로 바꾼 뒤에 탐색하도록 했습니다. (주석 처리가 된 함수 bfs_bindness)

그런데도 계속해서 틀렸습니다가 뜨네요.

현재는 미리 'G'를 'R'로 변경한 후에 똑같은 BFS 탐색을 하니 맞았다고 뜹니다.

두 가지의 코드 모두 결과는 똑같은데 정답 여부는 다르게 뜨네요.

왜 다른지 모르겠습니다. 접근법 때문인가요?

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct xy {
	int x; int y;
};

int n;

char map[101][101];
bool check[101][101];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };

int cnt = 0, cnt_bindness = 0;

void bfs(int y, int x) {
	queue<xy> q;
	xy src; src.x = x; src.y = y;
	
	q.push(src);
	check[y][x] = true;

	while (!q.empty()) {
		xy front = q.front();
		q.pop();

		char cur = map[front.y][front.x];

		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + front.x, ny = dy[i] + front.y;

			if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
				char next = map[ny][nx];
				if ((!check[ny][nx]) && cur == next) {
					xy next_char; next_char.x = nx; next_char.y = ny;
					q.push(next_char);
					check[ny][nx] = true;
				}
			}
		}
	}
}
/*
void bfs_bindness(int y, int x) {
	queue<xy> q;
	xy src; src.x = x; src.y = y;

	q.push(src);
	check[y][x] = true;

	while (!q.empty()) {
		xy front = q.front();
		q.pop();

		char cur = map[front.y][front.x];
		if (cur == 'G') {
			map[front.y][front.x] = 'R';
			cur = 'G';
		}
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + front.x, ny = dy[i] + front.y;

			if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
				char next = map[ny][nx];
				if (next == 'G') {
					map[ny][nx] = 'R';
					next = 'R';
				}

				if ((!check[ny][nx]) && cur == next) {
					xy next_char; next_char.x = nx; next_char.y = ny;
					q.push(next_char);
					check[ny][nx] = true;
				}
			}
		}
	}
}
*/
int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!check[i][j]) {
				cnt++;
				bfs(i, j);
			}
		}
	}

	memset(check, false, sizeof(check));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'G')
				map[i][j] = 'R';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!check[i][j]) {
				cnt_bindness++;
				bfs(i, j);
			}
		}
	}
	cout << cnt << " " << cnt_bindness << "\n";

	return 0;
}

bbwwpark 4년 전 1

61번째 줄에

cur = 'G'; 를 cur = 'R' 로 바꾸면 됩니다.

cur도 같이 바꿔줘야 합니다.

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

문제

문제

출처

ICPC

bfs 하면서 'G' 값을 바꿨는데 틀렸다고 뜹니다

aegamro 4년 전 0

bbwwpark 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말