글 읽기 - 알고스팟 질문입니다!

joungho512 6년 전 0

다이스트라 알고리즘을 이용해서 풀어야 하는 것은 알고있지만

bfs를 이용한 visit을 dp처럼 활용해서 풀어보려고 했습니다.

예제나 질문검색에 올라와 있던 테스트케이스를 돌려봤을때 제대로된 결과가 출력 되는것을

확인했는데 채점은 틀렸다고 나오는데 예외 케이스, 잘못된 부분 보이시면 알려주시면 감사하겠습니다

#include <stdio.h>
#include <queue>
#define INF 987654321
using namespace std;

int n,m;
int map[101][101];
int visit[101][101];
int max_cnt=INF;
int xd[4]= {1,-1,0,0};
int yd[4]= {0,0,1,-1};
bool ck(int y, int x)
{
	if( y<1 || x<1 || y> n || x >m) return false;
	return true;
}


int bfs()
{
	queue<int> q,qc;
	q.push(1*100+1);
	qc.push(0);
	visit[1][1]=0; // 시작지점

	int nx,ny,nc;
	
	while( !q.empty())
	{
		ny = q.front() / 100;
		nx = q.front() % 100;
		nc = qc.front();

		q.pop(); qc.pop();

		//printf("ny %d nx %d nc %d  \n",ny,nx,nc );
		if( ny == n && nx== m)
		{
			if(max_cnt > nc) max_cnt= nc;
		}
		int nex,ney;
		for(int i=0; i<4; i++)
		{
			nex= nx + xd[i];
			ney= ny + yd[i];

			if( !ck(ney,nex)) continue;
			
			if( map[ney][nex] == 0 && visit[ney][nex]> nc)
			{			
					q.push( ney * 100 + nex);
					qc.push(nc);
					visit[ney][nex]=nc;		
			} // map == 0 일때		
			else if( map[ney][nex] == 1 && visit[ney][nex] > nc+1)
			{			
					q.push( ney * 100 + nex);
					qc.push(nc+1);
					visit[ney][nex]=nc+1;			
			}
		}
	}
	printf("%d\n",max_cnt);
	return 0;
}

int main(void)
{
	scanf("%d %d",&m,&n);

	for(int i=1; i<=n;i++)
	{
		for(int j=1; j<=m;j++)
		{
			scanf("%1d",&map[i][j]);
		}
	}

	for(int i=0; i< 101; i++) for(int j=0; j<101; j++ ) visit[i][j]=INF;

	bfs();

	return 0;
}

kdk8361 6년 전 0

x, y 구분을 *100으로 하시는데 그러면 100x100 맵에서 오류가 발생하지 않나요?

joungho512 6년 전 0

map을 항상 0~99 배열로 받았었는데 1~100까지 받는 실수가 있었네요

수정해서 accept 받았습니다 감사합니다!

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

문제

문제

출처

ICPC

알고스팟 질문입니다!

joungho512 6년 전 0

kdk8361 6년 전 0

joungho512 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말