백준 2178 미로탐색

/*

BFS

어디에 있던

인접한 방들을 체크하는 것이 가장 중요

*/

/*

queue 사용법

삽입 queue.push(데이터);

가장 먼저 추가된 데이터 가져오기. queue.front();

가장 먼저 추가된 데이터를 삭제한다. queue.pop();

큐의 back을 리턴한다. back는 삭제되지 않는다. queue.back();

큐가 가지고 있는 항목의 수 queue.size();

큐가 비어 있는지 검사한다. queue.empty(); true : 큐에 항목이 없다

*/

#include <cstdio>

#include <iostream>

#include <queue>

void bfs(int x, int y);

using namespace std;

int N, M;

int arr[100][100] = { 0, };

int visit[100][100] = { 0, };

int dir[4][2] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

queue<int> QueueX;

queue<int> QueueY;

int length = 1;

int main()

{

cin >> N >> M;

for (int i = 0; i < N; i++){

for (int j = 0; j < M; j++){

//cin >> arr[i][j];

scanf("%1d", &arr[i][j]); //%1d를 사용하면 숫자 하나씩 읽을 수 있다.

}

}

bfs(0, 0);

printf("%d\n", visit[N - 1][M - 1]);

return 0;

}

void bfs(int x, int y)

{

int tempX, tempY;

visit[x][y] = 1;

QueueX.push(x);

QueueY.push(y);

while (!QueueX.empty() && !QueueY.empty()){

tempX = QueueX.front(); QueueX.pop();

tempY = QueueY.front(); QueueY.pop();

//전달 받은 좌표로 4방향 bfs 실행, 이미 방문한 곳은 제외한다.

for (int i = 0; i < 4; i++){

//미로 끝에 도착한다면

if ((tempX + dir[i][0] == N - 1) && (tempY + dir[i][1] == M - 1)){

visit[tempX + dir[i][0]][tempY + dir[i][1]] = visit[tempX][tempY] + 1;

return;

}

//맵 밖으로 나간다면, 

else if (tempX + dir[i][0] < 0 || tempX + dir[i][0]>99 || tempY + dir[i][1] < 0 || tempY + dir[i][1] >99)

continue;

//방문한적이 없고, 갈 수 있는 곳(1)이라면

else if ((visit[tempX + dir[i][0]][tempY + dir[i][1]] == 0)

&& (arr[tempX + dir[i][0]][tempY + dir[i][1]] == 1)){

QueueX.push(tempX + dir[i][0]);

QueueY.push(tempY + dir[i][1]);

visit[tempX + dir[i][0]][tempY + dir[i][1]] = visit[tempX][tempY] + 1;

}

}

}

}