글 읽기 - 메모리 초과 질문

cocogod 7년 전 0

그다음가야할 곳이 1 이면 있던값과 비교하고

0이면 그전값을 그대로 가저가는 BFS를 사용하였습니다.

값은 잘 나오는듯하나 메모리 문제로인해 통과를 하지 못하는군요....

제생각엔 큐에 많이 들어가다보니 메모리 문제 걸린듯 합니다.

이러면 DP를 써야할듯 한대 감이 안잡힙니다...

조금만 힌트를 나누어주세요 ㅠ

#include <stdio.h>
#include  <iostream>
#include <queue>
using namespace std;
#define INF 1000000
int n,m;
int maze[105][105];
int v[105][105];
int a[4] = {-1,0,1,0};
int b[4] = {0,1,0,-1};
void BFS(int row,int col){
    queue<pair<int,int> > q;
    q.push(make_pair(row, col));
     
    for(int i=0;i<105;i++)
        for(int j=0;j<105;j++)
            v[i][j] = INF;
    v[1][1] = 0;
    while(!q.empty()){
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        if(row == n && col == m)
            break;
         
        for(int i=0;i<4;i++){
            if(row+a[i] >=1 && row+a[i] <=n && col+b[i] >=1 && col+b[i] <=m){
                if(maze[row+a[i]][col+b[i]] == 1 && v[row+a[i]][col+b[i]] > v[row][col]+1){
                    v[row+a[i]][col+b[i]] = v[row][col]+1;
                    q.push(make_pair(row+a[i], col+b[i]));
                }else if(maze[row+a[i]][col+b[i]] == 0)
                {
                    q.push(make_pair(row+a[i], col+b[i]));
                    if(v[row+a[i]][col+b[i]] > v[row][col])
                    v[row+a[i]][col+b[i]] = v[row][col];
                }
                 
            }
        }
    }
     
     
}
 
int main(){
    cin >> m >> n;
     
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            scanf("%1d",&maze[i][j]);
    }
    BFS(1,1);
     
    printf("%d",min(v[n][m-1],v[n-1][m]));
}

joonas 7년 전 0

v[row][col]+1 을 함께 큐에 넣어보는건 어떨까요. 그리고 그것이 가장 작은것을 먼저 살피도록이요.

cocogod 7년 전 0

@joonas 우선순위큐를 이용하여 v[row][col]값이 작은것부터 꺼내서

비교하였습니다. 어차피 v값이 작은것 부터 확인하므로 한번방문한곳을 다시

방문안하게 해서 코드를 짯더니 74퍼에서 틀렷습니다. 가 나왔습니다.

제생각이 틀린것 인가요?

joonas 7년 전 0

생각은 맞는 것 같은데 74퍼라면 코드를 봐야할 것 같네요.

근데 출력하실때 printf("%d", v[n][m]); 가 아니라 근처를 하신 이유가 있나요?

cocogod 7년 전 1

@joonas 마지막은 무조건0이다 라는것때문에 근처만 확인해서 작은것을 확인했습니다.

그런대 printf("%d",v[n][m])하니 정답이내요!

감사합니다! ㅎㅎ

joonas 7년 전 1

처음에 초기화 하신거때문에

for(int i=0;i<105;i++)
for(int j=0;j<105;j++)
v[i][j] = INF;

아래 입력에서는 INF 가 나올것 같네요

1
0

해결되었다니 다행입니다! ㅎㅎ

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

문제

문제

출처

ICPC

메모리 초과 질문

cocogod 7년 전 0

joonas 7년 전 0

cocogod 7년 전 0

joonas 7년 전 0

cocogod 7년 전 1

joonas 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말