DFS로는 맞춰서 BFS로 풀어보았습니다!

인프런 커뮤니티 질문&답변

강민석

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-C

작성

156

수정됨

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;
}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 민석님 ㅎㅎ

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

강민석

작성한 질문수

전체 Q&A

질문하기