글 읽기 - 같은 형식 메모리초과

cyp0922 3년 전 0

코드는 거의 비슷한데 제코드는 메모리초과가 뜨고 다른 분이 푸신 코드는 통과합니다.

왜 제꺼는 메모리초과이고 다른 코드는 통과인지 궁금합니다 .,,

// 메모리 초과 코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<string>

using namespace std;

int N,M; 
string map[100];
int visited[100][100];


int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};



int dijkstra(){

	priority_queue<pair<int,pair<int,int> > > pq;
	pq.push(make_pair(0,make_pair(0,0)));
	visited[0][0] = true;	
	
	while(!pq.empty()){
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		int cnt = -pq.top().first;
		pq.pop();
		
		if(x==M-1 && y==N-1) return cnt;
		
		for(int i =0; i< 4; i++){
			int new_x = x + dx[i];
			int new_y = y + dy[i];
			
			if( new_x>=0 && new_x <M && new_y >=0 && new_y < N){
				if(!visited[new_x][new_y]){
					
					if(map[new_x][new_y] == '1'){
						pq.push(make_pair(-(cnt+1),make_pair(new_x,new_y)));
					}
					else{
						pq.push(make_pair(-(cnt),make_pair(new_x,new_y)));
						visited[new_x][new_y] = true;
					}
				}
			}
 		}
	}

}

int main(){
	int num;
	char input;
	scanf("%d %d",&N,&M);
	
	for(int i=0; i<M; i++ ){
		cin >> map[i];
	}
	
	printf("%d ",dijkstra() );

}




/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
// 통과 코드
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

using namespace std;
const int MAX = 100;
 
typedef struct
{
        int y, x;
}Dir;
 
Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

int M, N;
string input[MAX];
bool visited[MAX][MAX];

int BFS(void)

{

        //깨드린 블록을 기준으로 최소 힙 선언

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
        pq.push({ 0, {0, 0} });
        visited[0][0] = true;

        while (!pq.empty())
        {
                 int y = pq.top().second.first;
                 int x = pq.top().second.second;
                 int block = pq.top().first;
                 pq.pop();

                 if (y == N - 1 && x == M - 1)

                         return block;

                 for (int i = 0; i < 4; i++)
                 {

                         int nextY = y + moveDir[i].y;
                         int nextX = x + moveDir[i].x;

                         if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M)
                         {
                                 if (!visited[nextY][nextX])
                                 {

                                          if (input[nextY][nextX] == '1')
                                                  pq.push({ block + 1,{ nextY, nextX } });
                                          else
                                                  pq.push({ block, {nextY, nextX} });
                                          visited[nextY][nextX] = true;
                                 }
                         }
                 }
        }
}

int main(void)
{

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin >> M >> N;

        for (int i = 0; i < N; i++)
                 cin >> input[i];

        cout << BFS() << "\n";
        return 0;
}

출처: https://jaimemin.tistory.com/1049 [꾸준함]

kgstiger 3년 전 1

41~ 46 번째 줄에서 else 문에서만 방문처리하시고 if문에서는 방문처리가 안되서 그런것 같습니다.

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

문제

문제

출처

ICPC

같은 형식 메모리초과

cyp0922 3년 전 0

kgstiger 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말