[Silver I] 미로 탐색 - 2178

[Silver I] 미로 탐색 - 2178

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

이 문제는 가중치가 같은 그래프 내의 최단거리알고리즘 문제입니다.

BFS를 학습하고 처음으로 적용해서 풀었습니다.

한 줄씩 그래프를 입력받을 때 연결된 텍스트여서 문자열로 받고 캐릭터형을 하나씩 숫자로 변경해서 값을 받았습니다.

사실 가중치가 없는 그래프라 0과 1만 나오는 값이어서 삼항연산자를 사용할 수 있었으나 추후 가중치가 있는 그래프를 받았을 때도 대비해서 코드를 구성했습니다.

[Silver I] 미로 탐색 - 2178 풀이코드

#include <bits/stdc++.h>
using namespace std;

const int max_n = 104;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m, a[max_n][max_n], visited[max_n][max_n], y, x;
string s;
int main(void)
{
	scanf("%d %d", &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(y, x) = q.front(); q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + 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[y][x] + 1;
			q.push({ny, nx});
		}
	}
	
	cout << visited[n - 1][m - 1];
	
	return 0;
}