[Programmers] 리틀 프렌즈 사천성

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

프로그래머스

BFS 알고리즘을 이용하여 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. State 구조체는 좌표, 방향을 꺾은 횟수, 그리고 이전 방향을 저장하는 구조체입니다.

2. 전처리를 진행하는데 문제에서 가능한 경우 중 알파벳 순으로 가장 먼저인 케이스를 반환하라고 했으므로 주어진 배열 내 알파벳들을 set 자료구조에 저장해주고 각 알파벳의 위치를 v 벡터에 저장해줍니다.

3. set에 알파벳이 남아있는 한 계속 제거할 수 있는 타일이 존재하는지 확인합니다.

3.1 set을 순회하면서 해당 타일을 제거할 수 있는지 확인하고 제거할 수 있을 경우 해당 타일을 '.'으로 바꿔준 후 다시 3번을 반복합니다.

3.2 현재 상태에서 제거할 수 있는 타일이 없을 경우 불가능한 경우이므로 "IMPOSSIBLE"을 반환합니다.

 4. 사천성을 클리어했을 경우 answer를 반환해줍니다.

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <set>
	#include <map>
	#include <iostream>
	using namespace std;
	const int MAX = 100;
	typedef struct
	{
	int y, x;
	} Dir;
	typedef struct
	{
	int y, x;
	int cnt;
	int prevDir;
	} State;
	// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
	string solution(int m, int n, vector<string> board) {
	vector<pair<int, int>> v[26];
	Dir moveDir[4] = { { 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 } };
	set<char> characters;
	for (int i = 0; i < m; i++)
	{
	for (int j = 0; j < n; j++)
	{
	if (board[i][j] >= 'A' && board[i][j] <= 'Z')
	{
	characters.insert(board[i][j]);
	v[board[i][j] - 'A'].push_back({ i, j });
	}
	}
	}
	string answer = "";
	while (characters.size() > 0)
	{
	bool canErase = false;
	for (char c : characters)
	{
	pair<int, int> start = v[c - 'A'][0];
	pair<int, int> end = v[c - 'A'][1];
	queue<State> q;
	q.push({ start.first, start.second, -1, -1 });
	bool visited[MAX][MAX][3][4] = { false, };
	while (!q.empty())
	{
	State cur = q.front();
	int y = cur.y;
	int x = cur.x;
	int cnt = cur.cnt;
	int prevDir = cur.prevDir;
	q.pop();
	if (cnt >= 2)
	{
	continue;
	}
	if (y == end.first && x == end.second)
	{
	answer += c;
	characters.erase(c);
	canErase = true;
	board[start.first][start.second] = '.';
	board[end.first][end.second] = '.';
	break;
	}
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= m || nextX < 0 || nextX >= n)
	{
	continue;
	}
	if (prevDir != -1 && visited[nextY][nextX][cnt][prevDir]) {
	continue;
	}
	if (!(board[nextY][nextX] == c || board[nextY][nextX] == '.'))
	{
	continue;
	}
	visited[nextY][nextX][prevDir != k ? cnt + 1 : cnt][k] = true;
	q.push({ nextY, nextX, prevDir != k ? cnt + 1 : cnt, k });
	}
	}
	if (canErase)
	{
	break;
	}
	}
	if (canErase == false)
	{
	return "IMPOSSIBLE";
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

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