백준 2178 c++

오랫만에 포트폴리오 ai 작업을 시작하기전 코테문제를 풀어보기로 했다

시작은 간단하게 BFS 문제의 교과서라고 할수있는 2178문제

 

난이도 실버1

 

가중치가 1로 동일하고 최단거리를 찾는 문제이다

https://www.acmicpc.net/problem/2178

 

입력 & 출력

 

#include "iostream"
#include "tuple"
#include "queue"

using namespace std;

//가중치가 동일한 최단거리 -> bfs
//입력 n x m, 1 or 0
//출력 최단거리

const int max_Num = 104;

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

int n, m;
int a[max_Num][max_Num];
int visited[max_Num][max_Num];
int currentY, currentX;
string s;

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
			a[i][j] = s[j] - '0';
	}
	queue<pair<int, int>> q;
	visited[0][0] = 1;
	q.push({ 0, 0 });
	while (q.size())
	{
		tie(currentY, currentX) = q.front(); q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = currentY + dy[i];
			int nx = currentX + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0)
				continue;

			if (visited[ny][nx])
				continue;
			visited[ny][nx] = visited[currentY][currentX] + 1;
			q.push({ ny, nx });
		}
	}
	cout << visited[n - 1][m - 1];
	return 0;
}