[백준]Baekjoon2178(BFS)

문제링크 : https://www.acmicpc.net/problem/2178

이 문제에서는 BFS를 쓰면서 길이를 같이 계산할 수 있는 장치를 함께 두어야한다.

길이를 구하기 위해 만약 현재 좌표에서 갈 수 있는 다음 좌표가 아직 탐색되지 않았다면

현재좌표 + 1을 다음 좌표에 주는 방식으로 진행하였다.

그렇게 진행하다 보면 도착점이 탐색되자마자 설정된 숫자가 최단 길이가 된다.

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

using namespace std;

int arr[100][100];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int N, M;
int BFS()
{
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));

	int x, y;
	while (arr[N-1][M-1] == 1){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (arr[nx][ny] == 1) {
					arr[nx][ny] = arr[x][y] + 1;
					q.push(make_pair(nx, ny));
					if (nx == N - 1 && ny == M - 1) break;
				}
			}
		}
	}
	return arr[N-1][M-1];
}
int main()
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}

	printf("%d\n", BFS());
}