작성
·
156
·
수정됨
0
BFS로 풀었을 때 답은 맞는데 제출하면 메모리 초과로 틀렸다고 나오는데,
혹시 이 코드에서 메모리를 줄여서 맞힐 수 있는 방법이 있는지 여쭤보고 싶습니다!
#include<bits/stdc++.h>
using namespace std;
int N;
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
const int max_n = 100;
int arr[max_n][max_n];
int visited[max_n][max_n];
int x,y;
int Max = 0;
int main(){
cin >> N;
fill(&arr[0][0], &arr[0][0] + max_n*max_n, 0);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> arr[i][j];
}
}
for(int h = 1; h <= 100; h++){
int cnt = 0;
fill(&visited[0][0], &visited[0][0] + max_n*max_n, 0);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(arr[i][j] >= h && visited[i][j] == 0){
queue<pair<int,int>> q;
q.push({i,j});
cnt++;
while(q.size()){
tie(y,x) = q.front();
q.pop();
visited[y][x] = 1;
for(int n = 0; n < 4; n++){
int ny = y + dy[n];
int nx = x + dx[n];
if(ny < 0 || ny >= N || ny < 0 || ny >= N){
continue;
}
if(arr[ny][nx] < h){
continue;
}
if(visited[ny][nx]){
continue;
}
q.push({ny,nx});
}
}
}
}
}
Max = max(Max, cnt);
}
cout << Max;
return 0;
}
답변 1
0
안녕하세요 민석님 ㅎㅎ
bfs로는 이렇게 하시면 됩니다.
queue에 넣을 때는 반드시 visited를 걸고 넣는다라는 것을 명심해주세요.
#include<bits/stdc++.h>
using namespace std;
const int N_MAX = 100;
int N;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int arr[N_MAX][N_MAX];
int visited[N_MAX][N_MAX];
int Max = 0;
void bfs(int i, int j, int h) {
queue<pair<int, int>> q;
q.push({i, j});
visited[i][j] = 1;
while(!q.empty()) {
auto [y, x] = q.front();
q.pop();
for(int n = 0; n < 4; n++) {
int ny = y + dy[n], nx = x + dx[n];
if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if(arr[ny][nx] < h || visited[ny][nx]) continue;
q.push({ny, nx});
visited[ny][nx] = 1;
}
}
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
for(int h = 1; h <= 100; h++) {
fill(&visited[0][0], &visited[0][0] + N_MAX*N_MAX, 0);
int cnt = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(arr[i][j] >= h && visited[i][j] == 0) {
bfs(i, j, h);
cnt++;
}
}
}
Max = max(Max, cnt);
}
cout << Max;
return 0;
}
그리고 기존 코드에서
if(ny < 0 || ny >= N || ny < 0 || ny >= N){
이부분이 잘못되서 UB가 난 것 같습니다. 경계체크는 항상 주의해주세요. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.