시작

전에 DFS와 BFS를 이용해 푸는 문제다. 그렇다면 한번 확인해보자, 먼저 1은 이동할 있으며, 0은 이동할 수 없는 칸이다. 한번 예외사항을 우선 작성을 해보자

예외사항

1. 범위를 넘어선다면넘기기
2. 만약 한번이라도 방문했으면 넘기기
3. 방문하려는 땅이 방문할 수 없으면 넘기기

이런 예외사항을 가지고 한번 가중치가 있으며, 최단 위치 알고리즘을 구현가능한 BFS를 이용해서 한번 풀어보도록 하자. 우선 알고리즘을 한번 간단하게 짜보도록 하자.

알고리즘

1. 우선 4방향을 움직였을때 범위를 넘겼는지 확인
2. 만약 안넘겼으면 방문했는지 확인
3. 방문을 안했으면 그 땅으로 갈 수 있는지 확인
4. 방문이 가능하면 가중치+1

코드

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
#include<tuple>

using namespace std;

int dy[] = {- 1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int N, M, x, y;
vector<string> _map;
vector<vector<int>> visited;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	_map.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M);
	}

	for (int i = 0; i < N; i++) {
		cin >> _map[i];
	}

	queue<pair<int, int>> q;
	// 0, 0 부터 시작
	q.push({0, 0});
	visited[0][0] = 1;
	// q의 크기가 0일때 까지
	while (q.size()) {
		// y, x값 받고  front 없애기
		tie(y, x) = q.front(); q.pop();
		//4방향 체크
		for (int i = 0; i < 4; i++) {
			// 받아온 x, y값 dx[i], dy[i] 더해서 확인
			int nx = x + dx[i];
			int ny = y + dy[i];
			// 만약 범위가 벗어나면?
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			// 만약 한번 방문했거나, 그 위치가 0이라면?
			if (visited[ny][nx] >= 1) continue; if ((_map[ny][nx] - 48) == 0) continue;
			// 방문했으니 방문전 위치 + 1
			visited[ny][nx] = visited[y][x] + 1;
			// 다음을 위해 저장 해놓기
			q.push({ ny, nx });
		}
	}

	cout << visited[N - 1][M - 1];
}