• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

3-D 메모리초과 질문있습니다

24.04.17 16:57 작성 조회수 41

0

#include <bits/stdc++.h>

using namespace std;

int R, C, fire_visitied[1000][1000]={0,}, jihoon_visitied[1000][1000]={0,};
int dy[4]={-1,0,1,0}, dx[4]={0,1,0,-1}; 
char arr[1000][1000]={0,};
pair<int,int> jihoon, fire;
vector<pair<int,int>> fire_v;

void fire_bfs(int y, int x){
    queue<pair<int,int>> que;
    fire_visitied[y][x]=1;
    que.push({y,x});
    while(que.size()){
        pair<int,int> temp=que.front();
        que.pop();
        for (int i=0;i<4;i++){
            int ny=temp.first+dy[i];
            int nx=temp.second+dx[i];
            if (ny<0||nx<0||ny>=R||nx>=C) continue;
            if (arr[ny][nx]=='#'||(fire_visitied[ny][nx]&&(fire_visitied[ny][nx]<fire_visitied[temp.first][temp.second]+1))) continue;
            fire_visitied[ny][nx]=fire_visitied[temp.first][temp.second]+1;
            que.push({ny,nx});
        }
    }
}

int jihoon_bfs(int y, int x){
    queue<pair<int,int>> que;
    jihoon_visitied[y][x]=1;
    que.push({y,x});
    while(que.size()){
        pair<int,int> temp=que.front();
        que.pop();
        for (int i=0;i<4;i++){
            int ny=temp.first+dy[i];
            int nx=temp.second+dx[i];
            if (ny<0||nx<0||ny>=R||nx>=C) return jihoon_visitied[temp.first][temp.second];
            if (jihoon_visitied[ny][nx]||arr[ny][nx]=='#') continue;
            if (jihoon_visitied[temp.first][temp.second]+1>=fire_visitied[ny][nx]) continue;
            jihoon_visitied[ny][nx]=jihoon_visitied[temp.first][temp.second]+1;
            que.push({ny,nx});
        }
    }
    return 0;
}

int main()
{
    cin >> R >> C;

    for (int i=0;i<R;i++){
        for (int j=0;j<C;j++){
            cin >> arr[i][j];
            if (arr[i][j]=='J') jihoon={i,j};
            if (arr[i][j]=='F') fire_v.push_back({i,j});
        }
    }
    if (!fire_v.size()) fill(&fire_visitied[0][0],&fire_visitied[0][0]+1000*1000,INT_MAX);
    
    for (auto i:fire_v) fire_bfs(i.first,i.second);

    int answer=jihoon_bfs(jihoon.first,jihoon.second);

    if (answer) cout << answer;
    else cout << "IMPOSSIBLE";
}

위 코드에서 메모리 초과가 납니다. 초기의 모든 불의 위치를 큐에 담아서 bfs 를 하는 것을 생각하지 못해 모든 불을 돌면서 bfs를 하도록 코딩했습니다. 

if (arr[ny][nx]=='#'||(fire_visitied[ny][nx]&&(fire_visitied[ny][nx]<fire_visitied[temp.first][temp.second]+1))) continue;

이 라인을 통해서 fire 배열의 중복을 막은 것 같은데 왜 메모리초과가 나는지 모르겠습니다. 알려주시면 감사하겠습니다 ㅠ

course-thumbnail

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

3-D와 반례

강의실 바로가기

답변 1

답변을 작성해보세요.

0

큰돌님의 프로필

큰돌

지식공유자

2024.04.19

안녕하세요 ㅎㅎ

사실 그부분만 빼면 괜찮은 코드입니다.

저도 처음에는 그 부분 살려가면서 고치려고 했는데 왜인지 모르게 메모리초과나 틀렸습니다가 뜨더군요.

그럴 때 저는 보통 코드 다듬기를 합니다.

일단.. 저부분은 일단은 비효율적이기 때문에 다듬고.. 다른 부분도 최대한 수강생님 코드 살려가면서 다듬어봤는데요. 

#include <bits/stdc++.h>
using namespace std;

int R, C;
int fire_visited[1004][1004];
int jihoon_visited[1004][1004];
int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
char arr[1004][1004];
pair<int, int> jihoon;
vector<pair<int, int>> fire_v;

void bfs_fire() {
    queue<pair<int, int>> q;
    for (auto &f : fire_v) {
        q.push(f);
        fire_visited[f.first][f.second] = 1;
    }

    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny >= 0 && nx >= 0 && ny < R && nx < C && arr[ny][nx] != '#' && (!fire_visited[ny][nx] || fire_visited[ny][nx] > fire_visited[y][x] + 1)) {
                fire_visited[ny][nx] = fire_visited[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
}

int bfs_jihoon() {
    queue<pair<int, int>> q;
    q.push(jihoon);
    jihoon_visited[jihoon.first][jihoon.second] = 1;

    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= R || nx >= C) return jihoon_visited[y][x]; 
            if (!jihoon_visited[ny][nx] && arr[ny][nx] != '#' && (fire_visited[ny][nx] == 0 || jihoon_visited[y][x] + 1 < fire_visited[ny][nx])) {
                jihoon_visited[ny][nx] = jihoon_visited[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
    return 0;  
}

int main() {
    cin >> R >> C;
    memset(fire_visited, 0, sizeof(fire_visited));

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'J') jihoon = {i, j};
            else if (arr[i][j] == 'F') {
                fire_v.push_back({i, j});
                fire_visited[i][j] = 1;
            }
        }
    }

    bfs_fire();  
    int answer = bfs_jihoon(); 

    if (answer) cout << answer;
    else cout << "IMPOSSIBLE";

    return 0;
}

 

이렇게 한번 해보시겠어요?

전체적인 로직은 정말 잘 짜셨습니다. ㅎㅎ

틀린부분을 명확하게 알려주고 싶은데 마음대로 되지 않네요.

그래도 최대한 다듬어 봤습니다. ㅎㅎ

 


또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


이 글과 비슷한 Q&A