미로 탐색(백준)
전형적인 미로찾기 문제
#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)
이 구조 익히기
Author And Source
이 문제에 관하여(미로 탐색(백준)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@imalive77/미로-탐색백준저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)