글 읽기 - 이 코드는 왜 안전한 칸의 개수를 출력하나요?

(追記) (追記ここまで)

이 코드는 왜 안전한 칸의 개수를 출력하나요?

2468번 - 안전 영역

jeongdnjs 1년 전 0

안녕하세요.

저는 안전한 지역의 덩어리 개수를 카운트하는 코드를 작성했습니다.

하지만 예시 입력을 해보니 25가 출력되었습니다.

출력값을 보니 grid에서 안전한 칸을 모두 카운트하는 것으로 보였습니다.

이와 거의 동일하게 알고리즘을 활용한 다른 코드는 잘 작동하던군요,,

해당 코드의 문제점은 무엇입니까?

// 이 코드는 왜 덩어리의 개수를 출력하지 않는 것인가
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
vector<vector<int>> grid;
vector<vector<bool>> visited;
vector<int> cnt(101, 0);
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
void bfs(int x, int y, int max) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[x][y] = true;
	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curx + dx[i];
			int ny = cury + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] > max) {
				q.push({ nx, ny });
				visited[nx][ny] = true;
			}
		}
	}
}
void grid_cnt(int max) {
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	cnt[max] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] > max && !visited[i][j]) {
				bfs(i, j, max);
				cnt[max]++;
			}
		}
	}
}
int main() {
	cin >> n;
	grid.assign(n, vector<int>(n));
	visited.assign(n, vector<bool>(n, false));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
		}
	}
	for (int i = 0; i < 101; i++) {
		grid_cnt(i);
	}
	int maxClusters = *max_element(cnt.begin(), cnt.end());
	cout << maxClusters << endl;
}

g072923 1년 전 1

11 번쨰 줄의 visited 와 39 번쨰 줄의 visited는 서로 다른 변수로 인식됩니다. 같은 이름의 전역 변수와 지역 변수가 있을 경우 지역 변수가 우선시 됩니다.

따라서 grid_cnt 함수 내에서 max가 0으로 주어진 경우 44번쨰 줄의 조건문이 모두 참으로 인식되어 5*5 = 25 의 출력을 가지게 됩니다.

해결 방법으로는 grid_cnt 함수 내에서 visited 를 선언 하는 것이 아닌 false로 값을 초기화 해주는 방식으로 39번 쨰 줄을

visited = vector<vector<bool>>(n, vector<bool>(n, false));

변경하면 올바른 출력을 가지게 됩니다.

jeongdnjs 1년 전 0

아,, 이해했습니다. 아직 초보자라 미흡한 부분이 많네요. 친절한 답변 감사합니다!

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

이 코드는 왜 안전한 칸의 개수를 출력하나요?

jeongdnjs 1년 전 0

g072923 1년 전 1

jeongdnjs 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말