[C++] 백준 1261. 알고스팟

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

1261번: 알고스팟

 

문제

아이디어

BFS 문제의 대표격 중 하나인 미로찾기 문제입니다.

그러나 시간 제한이 1초이기 때문에

O(N^2) 인 BFS로는 풀 수 없고,

O(N logN) 인 다익스트라 알고리즘을 이용해서 풀어야만 합니다.

 

맨 좌측 상단에서 시작해서

맨 우측 하단까지 어떻게 도달할 것인가?

에 대한 문제이고

 

1은 벽인데 필요하다면 벽을 부술수도 있습니다.

단, 벽을 최대한 적게 부수면서 도달하는 것이 목표입니다.

 

이때, pair를 이용해서 

(부수는 벽의 횟수, 좌표) 의 쌍을 저장하고,

 

부수는 벽의 횟수를 최소 힙으로 하여 우선순위큐를 돌리면 해결할 수 있을겁니다.

 

풀이

테이블의 정보를 저장하는 데이터 입니다.

가로, 세로, 테이블 정보

그리고 해당 좌표에 도달하기위해 부숴야할 최소 벽의 수 를 record 에 기록합니다.

 

 

테이블 정보를 입력하는 부분입니다.

입력이 띄어쓰기가 존재하지 않아 처음에 입력 로직을 작성할 때 당황했는데요..

string으로 하나씩 끊어가면서 읽었습니다.

 

 

로직 초기화 부분 입니다.

 

 

우선순위큐 pair 를 요소로 사용하려면

비교용 함수 객체를 만들어서 전달해야 합니다.

 

 

우선 순위큐 로직입니다.

특별할 건 없습니다.

 

출력입니다.

 

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

struct Pos
{
	Pos(int y, int x) : _y(y), _x(x) {}

	Pos operator+(const Pos& other)
	{
		return Pos(_y + other._y, _x + other._x);
	}

	int _y;
	int _x;
};

struct MyGreater
{
	bool operator()(const pair<int, Pos>& left, const pair<int, Pos>& right) const
	{
		return left.first > right.first;
	}
};

int height;
int width;

int table[101][101];
int record[101][101];

int main()
{
	/* 입력 */
	{
		cin >> width >> height;

		for (int y = 0; y < height; y++)
		{

			string input;
			cin >> input;

			int x = 0;
			while (input != "\0")
			{
				table[y][x] = input[0] - '0';
				x++;
				input.erase(input.begin());
			}
		}
	}

	/* 로직 */
	{
		/* record 를 초기화 */
		for (int y = 0; y < height; y++)
			for (int x = 0; x < width; x++)
				record[y][x] = 999;


		priority_queue<pair<int, Pos>, vector<pair<int, Pos>>, MyGreater> pq;
		record[0][0] = 0;
		pq.push(make_pair(0, Pos(0, 0)));

		Pos moveWeight[4] =
		{
			{0,1},
			{1,0},
			{0,-1},
			{-1,0}
		};

		while (!pq.empty())
		{
			int cnt = pq.top().first;
			Pos here = pq.top().second;

			pq.pop();

			if (here._y == height - 1 && here._x == width - 1)
				break;

			if (cnt > record[here._y][here._x])
				continue;

			for (int dir = 0; dir < 4; dir++)
			{
				Pos newPos = here + moveWeight[dir];
				int newCnt = cnt;

				if (newPos._y < 0 || newPos._y >= height)
					continue;

				if (newPos._x < 0 || newPos._x >= width)
					continue;

				if (table[newPos._y][newPos._x] == 1)
					newCnt++;

				if (newCnt < record[newPos._y][newPos._x])
				{
					record[newPos._y][newPos._x] = newCnt;
					pq.push(make_pair(newCnt, newPos));
				}
			}
		}
	}

	/* 출력 */
	{
		cout << record[height - 1][width - 1] << endl;
	}
}

 

전체 코드 입니다.

 

 

 

다익스트라를 처음 학습하면 풀 수 있을만한 기본문제였습니다.