미로 탐색(백준)

2843 단어 BFS알고리즘BFS

전형적인 미로찾기 문제

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 100;
int N, M;
int Chk[MAX][MAX] = { 0, };
int Arr[MAX][MAX];
int iResult[MAX][MAX];
int DirX[4] = { -1, 0, 1, 0 };
int DirY[4] = { 0, -1, 0, 1 };

queue<pair<int, int>> qTemp;
int iCount = 1;//맨처음 계산하는 부분은 1을 채워준다.

int iStartX = 0;
int iStartY = 0;

//vector<vector<int>> vTemp = { {1,0,1,1,1,1},{1,0,1,0,1,0},{1,0,1,0,1,1},{1,1,1,0,1,1} };

void BFS(int x, int y)
{
	Chk[x][y] = 1;
	iResult[x][y] = 1;
	qTemp.push(make_pair(x, y));

	while (!qTemp.empty())
	{
		x = qTemp.front().first;
		y = qTemp.front().second;
		qTemp.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + DirX[i];
			int ny = y + DirY[i];
			if ((Chk[nx][ny] == 0 ) && (nx >= 0) && (nx < N) && (ny >= 0) && (ny < M) && (Arr[nx][ny] == 1))//1. 방문 안했고, 2. X바운더리, Y바운더리 안넘고, 
			{
				Chk[nx][ny]= 1;
				qTemp.push(make_pair(nx, ny));
				iResult[nx][ny] = iResult[x][y]+1;
			}
		}
	}
}


int main()
{
	cin >> N ;//이부분 Y 
	cin >> M ;//이부분 X

	scanf("%d %d", &N, &M);

	/* 그래프 정보 입력 */
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Arr[i][j]);
		}
	}
	
	//for (int i = 0; i < N; i++)
	//{
	//	for (int j = 0; j < M; j++)
	//	{
	//		cin >> Arr[i][j];
	//	}
	//}
	
    BFS(0, 0);

	int OutData = iResult[N - 1][M - 1];
	cout << OutData;

	return 0;
}

이문제 백준답에 하면 안되는데, TestCase 는 제대로 나옴.
1. 방향 x,y Array정하기
2. 방문체크와, 방문길이 정하는 Chk, Arr이차원
3. 맨처음 push, while(!qTemp.empty()) -> 상하좌우 탐색 ->및 바운더리와 방문기록(0), 길이 통해져있어야하고(1)
4. 이 때 ㄱ. 큐에 push, 방문기록 체크 =1, 결과값 = 이전 결과값 +1 (result[nx][ny]=result[x][y]+1)
이 구조 익히기

좋은 웹페이지 즐겨찾기