[Programmers] 지게차와 크레인

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/388353

프로그래머스

 

BFS 알고리즘 문제였습니다.

컨테이너 제거 방법은 두 가지이며 두 케이스 모두 고려하여 구현하면 되는 문제였습니다.

• 요청 문자열 길이가 2인 케이스: 해당 알파벳과 일치하는 모든 컨테이너를 별도의 조건 없이 제거
• 요청 문자열 길이가 1인 케이스
  • 현재 창고 상태에서 접근 가능한 컨테이너만 제거
  • 접근 가능하다는 의미는 해당 컨테이너의 4면 중 적어도 한쪽이 창고 외부 또는 창고 외부와 연결된 빈 공간과 연결되어 있어야 한다는 의미

 

	#include <string>
	#include <vector>
	#include <queue>
	using namespace std;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	int solution(vector<string> storage, vector<string> requests) {
	int n = storage.size();
	int m = storage[0].size();
	for (auto req : requests)
	{
	char letter = req[0];
	if (req.size() == 2)
	{
	for (int y = 0; y < n; y++)
	{
	for (int x = 0; x < m; x++)
	{
	if (storage[y][x] == letter)
	{
	storage[y][x] = '.';
	}
	}
	}
	continue;
	}
	vector<vector<bool>> reachable(n, vector<bool>(m, false));
	queue<pair<int,int>> q;
	for (int y = 0; y < n; y++)
	{
	if (storage[y][0] == '.' && !reachable[y][0])
	{
	reachable[y][0] = true;
	q.push({y, 0});
	}
	if (storage[y][m - 1] == '.' && !reachable[y][m - 1])
	{
	reachable[y][m - 1] = true;
	q.push({y, m - 1});
	}
	}
	for (int x = 0; x < m; x++)
	{
	if (storage[0][x] == '.' && !reachable[0][x])
	{
	reachable[0][x] = true;
	q.push({0, x});
	}
	if (storage[n - 1][x] == '.' && !reachable[n - 1][x])
	{
	reachable[n - 1][x] = true;
	q.push({n - 1, x});
	}
	}
	while (!q.empty())
	{
	auto cur = q.front();
	q.pop();
	int y = cur.first;
	int x = cur.second;
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m)
	{
	continue;
	}
	if (storage[nextY][nextX] == '.' && !reachable[nextY][nextX])
	{
	reachable[nextY][nextX] = true;
	q.push({nextY, nextX});
	}
	}
	}
	for (int y = 0; y < n; y++)
	{
	for (int x = 0; x < m; x++)
	{
	if (storage[y][x] != letter)
	{
	continue;
	}
	bool accessible = false;
	if (y == 0 || y == n - 1
	|| x == 0 || x == m - 1)
	{
	accessible = true;
	}
	else
	{
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= n
	|| nextX < 0 || nextX >= m)
	{
	accessible = true;
	break;
	}
	if (storage[nextY][nextX] == '.' && reachable[nextY][nextX])
	{
	accessible = true;
	break;
	}
	}
	}
	if (accessible)
	{
	storage[y][x] = '.';
	}
	}
	}
	}
	int answer = 0;
	for (int y = 0; y < n; y++)
	{
	for (int x = 0; x < m; x++)
	{
	if (storage[y][x] != '.')
	{
	answer++;
	}
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~