백준1987번 알파벳 C++로 구현해보기

---

```

백준1987번 알파벳 C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1987번 풀이
2.  DFS를 이용한 보드내에서 움직이기

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

1987번: 알파벳

 

 

백준 1987번 알파벳은

난이도 중하 등급의 문제로서

 

행열을 입력받고

입력받은 행렬 사이즈의 행렬을

알파벳으로 채운다음

 

왼쪽 상단 구석에서 시작해서 방문한 칸은 다시 방문안하고, 방문한 알파벳은 다시 방문 안한다는 조건하에

몇칸을 최대 움직일수 있는지 구하는 문제입니다.

 

저는 해당문제를 깊이 우선 탐색으로 풀었으며

DFS 에 대해서 궁금하신 분은 아래에 링크에 방문하셔서 공부후 진행 하셔주시면 됩니다.

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

문제는 여기서 푸시면 됩니다

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

1987번: 알파벳

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

풀이의 경우

 

 

행과 열을 유저로 부터 받아주고

 

	void getRowAndColumnFromUser()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> rowNumber;
		ss >> columnNumber;
	}

 

알파벳으로 타일들을 행과 열을 기준으로 채워주고

	void getAlphaTilesFromUser()
	{
		boardTiles = new char* [rowNumber];
		visitedTiles = new bool* [rowNumber];

		for (int i = 0; i < rowNumber; ++i) 
		{ 
			std::string inputStr;
			std::getline(std::cin, inputStr);
			boardTiles[i] = new char[columnNumber];
			visitedTiles[i] = new bool[columnNumber];
			
			std::stringstream ss(inputStr);

			for (int j = 0; j < columnNumber; ++j)
			{
				char tempVal;
				ss >> tempVal;
				boardTiles[i][j] = tempVal;
				visitedTiles[i][j] = false;
			}
		}
	}

 

DFS 를 이용해 답을 구해줍니다.

0, 0 이 제일 왼쪽 구석이고

재귀적으로

0 , 0 에서 

(0 , 1), (1, 0) 등으로 계속 깊이를 우선적으로 탐험하고

방문했던 알파벳과 위치는 다시 방문 안합니다.

그렇게 탐색한 분기들끼리 서로 비교해서

큰 값을 받아오면 최대 값을 구할수 있습니다.

	void findMaxMove()
	{
		const int startPosX = 0;
		const int startPosY = 0;
		int maxCnt = 0;
		std::cout << DFS(startPosX, startPosY);
	}

	int DFS(const int x, const int y)
	{
		int retVal = 0;

		if ((x >= 0 && x < rowNumber) && (y >= 0 && y < columnNumber) && (visitedTiles[x][y] == false))
		{
			const int tempVal = boardTiles[x][y] - 'A';
			if (visitedAlphabet[tempVal] == false)
			{
				visitedTiles[x][y] = true;
				visitedAlphabet[tempVal] = true;
				const int maxVal1 = std::max(DFS((x + dx[0]), (y + dy[0])), DFS((x + dx[1]), (y + dy[1])));
				const int maxVal2 = std::max(DFS((x + dx[2]), (y + dy[2])), DFS((x + dx[3]), (y + dy[3])));
				retVal = std::max(maxVal1, maxVal2) + 1;
				visitedAlphabet[tempVal] = false;
				visitedTiles[x][y] = false;
			}
		}

		return retVal;
	}

 

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include<numeric>

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


class CAlphaBoard
{
private:
	/* 행 */
	int rowNumber;
	/* 열 */
	int columnNumber;

	/* 보드 타일들 */
	char** boardTiles;
	/* 방문한 타일들*/
	bool** visitedTiles;
	/* 방문한 알파벳*/
	bool visitedAlphabet[26];

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

public:
	CAlphaBoard()
	{
		rowNumber = 0;
		columnNumber = 0;
		boardTiles = nullptr;
		visitedTiles = nullptr;

		for (int i = 0; i < 26; i++)
		{
			visitedAlphabet[i] = false;
		}

	}

	~CAlphaBoard()
	{
		/* 메모리 관리 */
		for (int i = 0; i < rowNumber; ++i)
		{ 
			delete[] boardTiles[i];
		} 
		delete[] boardTiles;

		for (int i = 0; i < rowNumber; ++i)
		{
			delete[] visitedTiles[i];
		}
		delete[] visitedTiles;
		

	}

	void getRowAndColumnFromUser()
	{
		/* 입력 속도를 줄여서 시간제한을 통과하기 위해서 stringstream 사용*/
		std::string inputStr;
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		ss >> rowNumber;
		ss >> columnNumber;
	}

	void getAlphaTilesFromUser()
	{
		boardTiles = new char* [rowNumber];
		visitedTiles = new bool* [rowNumber];

		for (int i = 0; i < rowNumber; ++i) 
		{ 
			std::string inputStr;
			std::getline(std::cin, inputStr);
			boardTiles[i] = new char[columnNumber];
			visitedTiles[i] = new bool[columnNumber];
			
			std::stringstream ss(inputStr);

			for (int j = 0; j < columnNumber; ++j)
			{
				char tempVal;
				ss >> tempVal;
				boardTiles[i][j] = tempVal;
				visitedTiles[i][j] = false;
			}
		}
	}

	void findMaxMove()
	{
		const int startPosX = 0;
		const int startPosY = 0;
		int maxCnt = 0;
		std::cout << DFS(startPosX, startPosY);
	}

	int DFS(const int x, const int y)
	{
		int retVal = 0;

		if ((x >= 0 && x < rowNumber) && (y >= 0 && y < columnNumber) && (visitedTiles[x][y] == false))
		{
			const int tempVal = boardTiles[x][y] - 'A';
			if (visitedAlphabet[tempVal] == false)
			{
				visitedTiles[x][y] = true;
				visitedAlphabet[tempVal] = true;
				const int maxVal1 = std::max(DFS((x + dx[0]), (y + dy[0])), DFS((x + dx[1]), (y + dy[1])));
				const int maxVal2 = std::max(DFS((x + dx[2]), (y + dy[2])), DFS((x + dx[3]), (y + dy[3])));
				retVal = std::max(maxVal1, maxVal2) + 1;
				visitedAlphabet[tempVal] = false;
				visitedTiles[x][y] = false;
			}
		}

		return retVal;
	}

	void printAlphaTiles()
	{
		for (int i = 0; i < rowNumber; ++i)
		{
			for (int j = 0; j < columnNumber; ++j)
			{
				std::cout << boardTiles[i][j] <<" ";
			}
			std::cout << std::endl;
		}
	}




};

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

	CAlphaBoard* cAlphaBoard = new CAlphaBoard();

	cAlphaBoard->getRowAndColumnFromUser();
	cAlphaBoard->getAlphaTilesFromUser();
	cAlphaBoard->findMaxMove();
	//cAlphaBoard->printAlphaTiles();


}

 

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---