글 읽기 - 2206번 어디가 문제인지 알고싶습니다.

slowsnail 4년 전 0

어디가 문제인지 알고싶습니다.

#include <iostream>
#include <cstring>
#include <queue>
#include <stdio.h>

int N;
int M;
bool map[1000][1000];
int find[1000][1000][2];

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

int bfs(){
    find[0][0][0]=1;
    find[0][0][1]=1;
    std::queue<std::pair<bool, std::pair<int, int>>> q;
    q.push(std::make_pair(false, std::make_pair(0,0)));

	
    while(!q.empty()){
    	
        bool used=q.front().first;
        int ypos=q.front().second.first;
        int xpos=q.front().second.second;
        
        if(ypos==N-1 && xpos==M-1) return find[ypos][xpos][used];
        q.pop();

        for(int i=0; i<4; i++){
            int ny=ypos+dy[i];
            int nx=xpos+dx[i];

            if(ny<0 || nx<0 || N<=ny || M<=nx) continue;

            if(map[ny][nx]==0 && find[ny][nx][used]==-1){
                q.push(std::make_pair(used, std::make_pair(ny, nx)));
                find[ny][nx][used]=find[ypos][xpos][used]+1;
            }
            else if(map[ny][nx]==1 && !used && find[ny][nx][true]==-1){
                q.push(std::make_pair(true, std::make_pair(ny, nx)));
                find[ny][nx][true]=find[ypos][xpos][used]+1;
            }
        }

    }


    
    return -1;
}

int main(){
    std::cin>>N>>M;
    std::memset(find, -1, sizeof(find));
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    std::cout<<bfs();

}

jhwan818 3년 전 1

8,9번줄 배열 범위가 잘못됬어요! 각각 [1001][1001]로 수정해주세요!

문제 범위를 잘 살펴보세요! (1 ≤ N, M ≤ 1,000)

slowsnail 3년 전 0

답변해 주신대로 범위를 바꿨더니 통과가 됐습니다.

그런데 입력받은 (y, x)위치를 (y-1, x-1)위치에 저장시키는 코드를 구상했는데 배열 범위가 잘못되었다는게 이해가 되지 않아서 어디서 문제가 발생했는지 추적해 봤습니다.

그러다 범위를 원래대로 유지했을때 map 입력이 제대로 되지 않는것을 발견했고 원인을 찾아나가다 전역변수 N, M의 선언 위치를 변경하자 문제가 해결 되는 것을 확인했습니다.

전역변수의 선언 위치에 따라 어떻게 입력이 제대로 되지 않을 수 있는건지 알고싶습니다.

#include <iostream>
#include <cstring>
#include <queue>
#include <stdio.h>


bool map[1000][1000];
int find[1000][1000][2];

//int N;                    // 주석을 해제하고 16 17번 줄을 주석처리하면 문제가 발생한다
//int M;

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

int N;
int M;

int bfs(){
	std::memset(find, -1, sizeof(find));
    find[0][0][0]=1;
    find[0][0][1]=1;
    std::queue<std::pair<bool, std::pair<int, int>>> q;
    q.push(std::make_pair(false, std::make_pair(0,0)));

	
    while(!q.empty()){
        bool used=q.front().first;
        int ypos=q.front().second.first;
        int xpos=q.front().second.second;
        q.pop();
        
        if(ypos==N-1 && xpos==M-1) return find[ypos][xpos][used];

        for(int i=0; i<4; i++){
            int ny=ypos+dy[i];
            int nx=xpos+dx[i];

            if(ny<0 || nx<0 || N<=ny || M<=nx) continue;

            if(map[ny][nx]==0 && find[ny][nx][used]==-1){
                q.push(std::make_pair(used, std::make_pair(ny, nx)));
                find[ny][nx][used]=find[ypos][xpos][used]+1;
            }
            if(map[ny][nx]==1 && !used && find[ny][nx][true]==-1){
                q.push(std::make_pair(true, std::make_pair(ny, nx)));
                find[ny][nx][true]=find[ypos][xpos][used]+1;
            }
        }

    }

    return -1;
}

int main(){
    std::cin>>N>>M;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%1d",&map[i][j]);
        }
    }

    std::cout<<bfs();

}

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

문제

문제

출처

ICPC

2206번 어디가 문제인지 알고싶습니다.

slowsnail 4년 전 0

jhwan818 3년 전 1

slowsnail 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말