나의 브을로오그으

[c++] 2178번 : 미로 탐색 본문

알고리즘/BaekJoon

[c++] 2178번 : 미로 탐색

__jhp_+ 2022. 6. 23. 11:27

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

#define MAX_SIZE		101

int GetMoveCountOfMaze(int maze[][MAX_SIZE], int endX, int endY);

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

	int mazes[MAX_SIZE][MAX_SIZE] = { 0, };
	int N = 0, M = 0, count = 0;
	char input[MAX_SIZE] = { 0, };
	cin >> N >> M;
	cin.ignore();
	for (int i = 1; i <= N; ++i)
	{
		cin.getline(input, MAX_SIZE);
		for (int j = 1; j <= M; ++j)
		{
			mazes[i][j] = input[j-1] - '0';
		}
	}
	count = GetMoveCountOfMaze(mazes, M, N);
	cout << count << '\n';

	return 0;
}

int GetMoveCountOfMaze(int mazes[][MAX_SIZE], int endX, int endY)
{
	int dir[2][4] = { { -1, 0, 1, 0 }, {0, 1, 0, -1} };
	bool passed[MAX_SIZE][MAX_SIZE] = { false, };
	queue<pair<int, int>> log;
	int beginX = 1, beginY = 1, count = 0;

	log.push(make_pair(beginX, beginY));
	passed[beginX][beginY] = true;
	++count;
	while (log.empty() == false)
	{
		int size = log.size();
		for (int i = 0; i < size; ++i)
		{
			int x = 0, y = 0;
			pair<int, int> curPos = log.front();
			log.pop();
			for (int j = 0; j < 4; ++j)
			{
				x = curPos.first + dir[0][j];
				y = curPos.second + dir[1][j];
				if (x == endX && y == endY)
				{
					return ++count;
				}
				else if (x <= 0 || y <= 0 || x > endX || y > endY)
				{
					continue;
				}
				else if (passed[y][x] == false && mazes[y][x] == 1)
				{
					log.push(make_pair(x, y));
					passed[y][x] = true;
				}
				else
				{
					/* Nothing */
				}
			}
		}
		++count;
	}

	return count;
}

'알고리즘 > BaekJoon' 카테고리의 다른 글

[c++] 2606번 : 바이러스  (0) 2022.06.28
[c++] 2579번 : 계단 오르기  (0) 2022.06.27
[c++] 1992번 : 쿼드트리  (0) 2022.06.23
[c++] 1931번 : 회의실 배정  (0) 2022.06.22
[c++] 1927번 : 최소 힙  (0) 2022.06.21