글 읽기 - 2206 bool visited을 q에 포함시킬 수 없는지..

mollang99 3년 전 0

인터넷에 보니 다들 bool visited 배열을 사용하셔서 방문했는지 안했는지 체크하시더라구요.

근데 저는 방문했는지를 왜 체크하는지 잘 모르겠습니다.

저는 breaky라는 변수로 q에 넣어두었기 때문에 상관없다고 생각하고 있습니다..

친구가 준 테스트 케이스에서도 틀려서 틀린건 알겠는데 이해가 안갑니다ㅠㅠ

도와주시면 감사하겠습니다ㅠㅠㅠㅠㅠㅠ

<친구가 준 tc>

5 5

01000

00011

01110

11111 저는 여기서 -1이 나옵니다..

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int arr[1001][1001] = { 0, };
int xx[4] = {0,0,-1,1};
int yy[4] = {-1,1,0,0};
int N, M;
queue<pair<pair<pair<int,int>,int>,int > >q;

int bfs(){
	q.push(make_pair(make_pair(make_pair(0,0),1),0));
	arr[0][0] = 5;

	while(!q.empty()){
		int frontx = q.front().first.first.first;
		int fronty = q.front().first.first.second;
		int cnt = q.front().first.second;
		int breaky = q.front().second;
		q.pop();
		if(frontx == N-1 && fronty == M-1){
			return cnt;
		}
		else{
			for(int i = 0; i < 4; i++){
				if(0<=frontx+xx[i]&&frontx+xx[i]<N && 0<=fronty+yy[i]&&fronty+yy[i]<M){
					if(arr[frontx+xx[i]][fronty+yy[i]] == 0){
						q.push(make_pair(make_pair(make_pair(frontx+xx[i],fronty+yy[i]),cnt+1),breaky));
						arr[frontx+xx[i]][fronty+yy[i]] = 5;
					}
					else if(arr[frontx+xx[i]][fronty+yy[i]] == 1 && breaky == 0){
						q.push(make_pair(make_pair(make_pair(frontx+xx[i],fronty+yy[i]),cnt+1),1));
						arr[frontx+xx[i]][fronty+yy[i]] = 5;
					}
				}
			}
		}
	}
	return -1;
}

int main(){
	string tmp;
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		cin >> tmp;
		for(int j = 0; j < M; j++){
			arr[i][j] = tmp[j] - '0';
		}
	}

	int result = bfs();

	cout << result;
	return 0;
}

shg9411 3년 전 0

벽을 부쉈는지에 상관없이, 최단거리로 가야하기 때문에 방문여부를 체크하면서 나아가야 합니다.

또한 친구분이 주신 테스트케이스는 -1이 출력되는 것이 맞는 것 같습니다.

cgin1202 3년 전 0

시작점과 끝점은 0이어야 합니다.

친구분이 주신 tk는 끝점이 1이네요..

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

문제

문제

출처

ICPC

2206 bool visited을 q에 포함시킬 수 없는지..

mollang99 3년 전 0

shg9411 3년 전 0

cgin1202 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말