글 읽기 - 2178 bfs이용해서 구현했는데 어디서 틀렸을까요..?

qwq713 6년 전 0

아무리봐도모르겠네요...

어디가 틀린걸까요 ? ㅜ

#include<stdio.h>
#include<queue>
using namespace std;
int inputarray[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
//상 하 좌 우


//inputarray
//0: 길이 막혀있음 1: 길이 존재함 2:길 존재하는데 이미 한번 지나간 길
//resultarray
//해당 위치에 도달하기까지의 걸음 수

//-1로초기화하는함수

typedef struct xy {
	int y;
	int x;
	int cnt;
}xy;

int main(void) {
	int n, m;
	queue<xy> q;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &inputarray[i][j]);
			//숫자가 붙어서 입력되므로 이런식으로 받아야함 stdio.h include해줄 것.
		}
	}

	xy start = { 1,1 ,1};
	q.push(start);

	while (!q.empty()) {
		xy front = q.front();//현재온길
		if (front.y == n && front.x == m) {
			printf("%d\n",front.cnt);
			//while (1);
			return 0;
		}
		inputarray[front.y][front.x] = 2;//왔다는것을 체크
		int number = front.cnt;//현재 위치의 발걸음수를 기억
		q.pop();//현재위치 큐에서 제거.
		for (int i = 0; i < 4; i++) {
			xy nextxy;
			nextxy.y = front.y + dy[i];
			nextxy.x = front.x + dx[i];//현재위치에서 갈수있는 위치 중 하나.
			if (1 <= nextxy.x && nextxy.x <= m && 1 <= nextxy.y && nextxy.y <= n && inputarray[nextxy.y][nextxy.x] == 1) {
				nextxy.cnt = front.cnt + 1;
				q.push(nextxy);
			}
		}
	}
}

djm03178 6년 전 1

https://www.acmicpc.net/blog/v... 이 글에서 이 코드의 문제점을 찾을 수 있습니다.

qwq713 6년 전 0

감사합니다 덕분에 입출력이 틀렸다는걸 발견했어요! 근데 요번엔 메모리초과가뜨네요.. 보통

메모리 초과가 나면 코드의 어떤 부분을 수정해야하나요 ? .. ?답변주시면 감사하겠습니다 ㅜㅜ

djm03178 6년 전 1

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다.

qwq713 6년 전 0

지전....지려버렸습니다..

qwq713 6년 전 0

최종본입니다 감사합니다!!!

#include<stdio.h>
#include<queue>
using namespace std;
int inputarray[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
//상 하 좌 우


//inputarray
//0: 길이 막혀있음 1: 길이 존재함 2:길 존재하는데 이미 한번 지나간 길
//resultarray
//해당 위치에 도달하기까지의 걸음 수

//-1로초기화하는함수

typedef struct xy {
	int y;
	int x;
	int cnt;
}xy;

int main(void) {
	int n, m;
	queue<xy> q;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &inputarray[i][j]);
			//숫자가 붙어서 입력되므로 이런식으로 받아야함 stdio.h include해줄 것.
		}
	}

	xy start = { 1,1 ,1};
	q.push(start);

	while (!q.empty()) {
		xy front = q.front();//현재온길
		if (front.y == n && front.x == m) {
			printf("%d\n",front.cnt);
			//while (1);
			return 0;
		}
		int number = front.cnt;//현재 위치의 발걸음수를 기억
		q.pop();//현재위치 큐에서 제거.
		for (int i = 0; i < 4; i++) {
			xy nextxy;
			nextxy.y = front.y + dy[i];
			nextxy.x = front.x + dx[i];//현재위치에서 갈수있는 위치 중 하나.
			if (1 <= nextxy.x && nextxy.x <= m && 1 <= nextxy.y && nextxy.y <= n && inputarray[nextxy.y][nextxy.x] == 1) {
				nextxy.cnt = front.cnt + 1;
				inputarray[nextxy.y][nextxy.x] = 2;//왔다는것을 체크
				q.push(nextxy);
			}
		}
	}
}

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

문제

문제

출처

ICPC

2178 bfs이용해서 구현했는데 어디서 틀렸을까요..?

qwq713 6년 전 0

djm03178 6년 전 1

qwq713 6년 전 0

djm03178 6년 전 1

qwq713 6년 전 0

qwq713 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말