Baekjoon1987-알파벳

백준 사이트 1987 - 알파벳 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DFS문제입니다.
BFS로는 풀기 어렵다고 생각합니다. 이유는 밑에 쓰겠습니다.
백준에서는 Gold4 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 삽질을 엄청 많이한 문제입니다.
• BFS로 풀어볼까?
  • BFS는 자신이 있으니까 BFS로 구현해볼까 했습니다. 실제로 ‘치즈’ 문제도 DFS로 분류되어 있지만 BFS 풀었기 때문입니다. BFS로 풀기 힘든 이유는 너비 탐색 조건을 까다롭게 하기 때문입니다. 당장 첫 예제만 봐도 0,1과 1,0이 ‘A’라서 방문처리를 풀어줘야하는데 그 부분에서 어려움이 있습니다.
• DFS로 풀어야하는 것은 맞는데, 인자로 count를 넘길까?
  • 저는 인자를 많이 쓰는 것을 싫어해서.. 왜그런지 모르겠지만 2차원 DP를 만들어서 결과값들을 저장했습니다. 이 부분에서 엄청 애 썼는데 왠지 몰라도 오류가 많이 발생했습니다. 똥고집으로 해결하고 싶어서 30분 이상 썼습니다.
• 포기하고 인자로 count값을 넘기자. -> 해결

---

5. code

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

const int MAX = 22;
int r, c;

int result = 1;
char MAP[MAX][MAX] = { '0', };
bool check[30] = { false, };
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1};


void DFS(int i, int j,int count)
{
	result = max(result, count);
	check[MAP[i][j] - 65] = true;
	for (int k = 0; k < 4; ++k)
	{
		int newX = i + dx[k];
		int newY = j + dy[k];
		if (0 <= newX && newX < r && 0 <= newY && newY < c && !check[MAP[newX][newY]-65])
		{
			DFS(newX, newY,count+1);
			check[MAP[newX][newY] - 65] = false;	
		}
	}

}

void Input()
{
	cin >> r >> c;
	for (int i = 0; i < r; ++i)
	{
		cin>>MAP[i];
	}
}

void Solve()
{
	memset(check, false, sizeof(check));
	DFS(0, 0,1);
	cout << result;
}

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

	Input();
	Solve();
}

---

6. 후기

풀고 나니 어렵진 않은데 시간을 너무 써서 찝찝한 문제..