BOJ - 2178. 미로 (C++)

2178. BFS

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

2178번: 미로 탐색

 

[풀이]

각행의 수들은 붙어서 입력이 들어온다. 이러한 경우 이중 for문을 통해 입력받는 방법을 코드로 확인할 수 있다.

2차원 배열 board을 선언할 때부터 문자열의 배열로 선언할 수도 있지만 더욱 실수할 확률이 높다.

뿐만 아니라 각 칸의 dist 배열을 2차원으로 초기화하는데 이중 for문이 필요하기 때문에 같이 사용하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[502][502];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int dist[502][502];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; i++){
		string tmp; cin >> tmp;
		for (int j=0; j<m; j++) {
			board[i][j] = tmp[j] - '0';
			dist[i][j] = -1;
		}
	}
		
	queue<pair<int, int>> Q;
	Q.push({0,0});
	dist[0][0] = 0;
							
	while(Q.size()){
		pair<int,int> cur = Q.front(); Q.pop();
		for (int dir=0; dir<4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx >= n || nx < 0 || ny >= m || nx < 0) continue;
			if (dist[nx][ny]!=-1 || board[nx][ny]==0) continue;
			Q.push({nx,ny});
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
		}
	}
	cout << dist[n-1][m-1]+1;	
}