[백준 2178] 미로 탐색

난이도

실버 I

📜문제

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

🔎접근

한 칸씩 이동을 해서 그때의 거리를 측정하면서 목표지점에 도착했을때의 거리를 구하는 문제이므로 BFS를 사용해야한다.

🌞풀이

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

int result[MAX][MAX];
bool visited[MAX][MAX];
int dist[MAX][MAX]; //거리 배열

queue<pair<int, int>> q;
int row, col;

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

void BFS()
{
	int x = 0;
	int y = 0;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	dist[x][y] = 1;

	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
			if (result[nx][ny] == '1' && visited[nx][ny] == false)
			{
				q.push(make_pair(nx, ny));
				visited[nx][ny] = true;
				dist[nx][ny] = dist[x][y] + 1; // 거리 + 1
			}
		}
	}
}

int main()
{
	cin >> row >> col;

	string road;
	for (int i = 0; i < row; i++)
	{
		cin >> road;
		for (int j = 0; j < col; j++)
		{
			result[i][j] = road[j];
		}
	}

	BFS();
	cout << dist[row-1][col-1] << "\n";

	return 0;
}

이전의 좌표의 거리에서 한 칸 이동 했으므로 1을 더해주는것이 포인트

❗주의

전체 1의 개수를 구하는것이 아닌 그때의 거리를 구하는것이므로 거리를 배열에 저장하면서 가야한다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기