글 읽기 - BFS로 구현을 해보았는데, 답 제출시 틀렸네요 ㅠㅠ 도움요청합니당

daehyun6549 8년 전 1

소스코드 달아놨어여ㅎㅎ..

#include <stdio.h>


#define mxrws 101
#define myrws 101

typedef struct Queue {
	int x;
	int y;
	int weight;
}Queue;


char maze[mxrws][myrws];
int rows, cols;
int index = 0, level = 0;
int x_destination, y_destination;

void breadthfirstsearch(int _x, int _y, int _w);
void initMaze(int rows, int cols);


void initMaze(int rows, int cols) {
	x_destination = rows - 1;
	y_destination = cols - 1;

	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			maze[i][j] = '0';
		}
	}
}


void breadthfirstsearch(int _x, int _y, int _w) {
	Queue qu[10300];
	int min = rows*cols;



	qu[index].x = _x;
	qu[index].y = _y;
	qu[index].weight = _w;

	//탐색 함
	maze[qu[index].x][qu[index].y] = '0';


	//최종

	while (level <= index) {
		if ((qu[index].x == x_destination) && (qu[index].y == y_destination)) {
			if (min > qu[index].weight)
				min = qu[index].weight + 1;
		}



		//오른쪽
		if (maze[qu[level].x][qu[level].y + 1] == '1') {
			index++;

			qu[index].x = qu[level].x;
			qu[index].y = qu[level].y + 1;
			qu[index].weight = qu[level].weight + 1;

			maze[qu[index].x][qu[index].y] = '0';

		}

		//아래쪽
		if (maze[qu[level].x + 1][qu[level].y] == '1') {
			index++;

			qu[index].x = qu[level].x + 1;
			qu[index].y = qu[level].y;
			qu[index].weight = qu[level].weight + 1;

			maze[qu[index].x][qu[index].y] = '0';
		}

		//왼쪽
		if (maze[qu[level].x][qu[level].y - 1] == '1') {
			index++;

			qu[index].x = qu[level].x;
			qu[index].y = qu[level].y - 1;
			qu[index].weight = qu[level].weight + 1;

			maze[qu[index].x][qu[index].y] = '0';
		}

		//위쪽
		if (maze[qu[level].x - 1][qu[level].y] == '1') {
			index++;

			qu[index].x = qu[level].x - 1;
			qu[index].y = qu[level].y;
			qu[index].weight = qu[level].weight + 1;

			maze[qu[index].x][qu[index].y] = '0';
		}

		level++;

	}

	printf("%d\n", min);




}
int main() {

	//start : (0,0) end : (rows-1,cols-1)
	scanf("%d %d", &rows, &cols);
	initMaze(rows, cols);


	for (int i = 0; i < rows; i++) {
		scanf("%s", &maze[i]);
	}

	//시작점x, 시작점y, 처음 경로 횟수
	breadthfirstsearch(0, 0, 0);
	return 0;
}

cubalys 8년 전 0

if ((qu[index].x == x_destination) && (qu[index].y == y_destination)) {
            if (min > qu[index].weight)
                min = qu[index].weight + 1;
        }

index -> level 로 바꾸시면 맞습니다.

index로 검사하게 되면 전에 큐에 넣었던 위 아래 왼쪽 오른쪽중 하나만 검사하므로 틀릴 수 있습니다.

cubalys 8년 전 1

그리고 Bfs의 경우 깊이가 낮은 노드부터 방문하므로 목적지에 처음 도착했을 때가 최단경로가 됩니다.

if ((qu[level].x == x_destination) && (qu[level].y == y_destination)) {
min = qu[level].weight + 1;

break;
}

하셔도 최단 경로를 구할 수 있습니다.

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

문제

문제

출처

ICPC

BFS로 구현을 해보았는데, 답 제출시 틀렸네요 ㅠㅠ 도움요청합니당

daehyun6549 8년 전 1

cubalys 8년 전 0

cubalys 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말