백준 c++ 2178번

백준 2178번

 

board는 미로의 크기를 나타내는 배열, vis는 해당 지점을 방문했는지 나타는 배열, length는 시작 지점에서부터 해당 지점까지의 거리를 나타낸다.

 

n, m은 미로의 세로와 가로의 길이를 나타내고 한 줄씩 string 값을 입력받아 board에 저장한다.

 

첫번째 (0,0)을 큐에 넣고 vis[0][0]을 1로 바꾸고 이중for문을 사용하여 length 배열의 값들을 넣어준다. 마지막에 1을 더한 이유는 length에 저장되어 있는 값은 거리값이고 해당 문제에서 요구하는 것은 이동한 칸의 갯수이므로 +1을 해준다.

 

 

 

전체코드

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


using namespace std;

#define X first
#define Y second

int board[101][101] = { 0, };
bool vis[101][101];
int length[101][101] = { 0, };

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


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		int k = 0;
		for (int j = 0; j < m; j++) {
			board[i][j] = str[k] - '0';
			if (k < str.length() - 1)
				k++;
		}
	}

	queue<pair<int, int>> Q;
	vis[0][0] = 1;
	Q.push({ 0,0 });

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			while (!Q.empty()) {
				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 < 0 || nx >= n || ny < 0 || ny >= m)
						continue;
					if (vis[nx][ny] || board[nx][ny] != 1)
						continue;
					vis[nx][ny] = 1;
					length[nx][ny] = length[cur.X][cur.Y] + 1;
					Q.push({ nx,ny });
				}
			}
		}
	}
	cout << length[n-1][m-1] + 1;
	return 0;
}