백준 1926번 문제 질문드립니다.

Question

https://www.acmicpc.net/problem/1926언급된 모든 반례를 처리했으나 여전히 오답이라고 나옵니다. 도대체 어디부분이 잘못됐길래 오답인걸까요 ㅠㅠ#include #include #include #define MAX 500+3 using namespace std; int map[MAX][MAX]; int division[MAX * MAX]; bool visited[MAX][MAX]; int m, n, cnt, zeroCnt; int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, -1, 1 }; void bfs(int b, int a) { queue> q; q.push(make_pair(b, a)); visited[b][a] = true; 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 || ny >= n || nx >= m) continue; if (map[ny][nx] == 1 && !visited[ny][nx]) { visited[ny][nx] = true; division[cnt]++; q.push(make_pair(ny, nx)); } } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 1 && !visited[i][j]) { cnt++; division[cnt]++; bfs(i, j); } } } for (int i = 1; i <= cnt; i++) { if (division[i] == 0) { zeroCnt++; } } if (zeroCnt >= cnt) { cout << "0 0"; } else { cout << cnt << " "; sort(division + 1, division + (cnt + 1)); cout << division[cnt]; } return 0; }

yeori · Answer

폰이라 길게 쓰기는 힘들고, division 배열이 면적을 저장하는 용도같은데, 어차피 문제에서는 최대값만 구하라고 했으니까 bfs 함수가 면적을 반환하게 하고, main 에서는 bfs에서 반환받은 면적값을 비교해서 최대값을 갱신하는 식으로 수정하면 코드가 더 보기 편할듯 싶네요main 에서 bfs 를 호출한게 그림의 갯수이겠죠

아트99 · Answer

#define MAX 부분에서 500&#43;3 부분에 괄호를 치지 않아서 생긴 문제더라고요 ㅠㅠ 저는 저렇게 해놓으면 당연히 (500&#43;3) 으로 값이 들어갈줄 알았는데 500&#43;3 그대로 들어가서 division 을 선언하는 부분에서500&#43;3*500&#43;3 이 되버려서 실제 크기가 고작 2003 이 되서 범위가 맞지 않아서 계속 답이 틀리는거였습니다. MAX 부분에 있는 식을 괄호를 쳐주니깐 잘됩니다.

백준 1926번 문제 질문드립니다.

2개의 답변

#bfs 목록