[BOJ] 1987 알파벳

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

Note

DFS 문제

조건

1. 시작하는 칸도 포함 : 즉 최대값은 1부터 시작
2. 칸을 기준으로 중복 체크를 하는 것이 아닌 현재 칸의 알파벳을 밟은 적이 있는지를 검사

소스코드

#include <iostream>
#include <string>

using namespace std;

int posX[4] = { 1, 0, -1, 0 };
int posY[4] = { 0, 1, 0 , -1 };
char map[20][20];
int row, col;
int mMax = 1;

void algo(int x, int y, int step, bool alpha[26]) {

	if (alpha[map[x][y] - 'A'])
	{
		if (step > mMax)
			mMax = step;
	}

	alpha[map[x][y] - 'A'] = true;

	for (int i = 0; i < 4; i++) // Right, Bottom, Left, Top
	{
		if (0 <= x + posX[i] && x + posX[i] < row && 0 <= y + posY[i] && y + posY[i] < col)
		{
			int idx = int(map[x + posX[i]][y + posY[i]]) - 'A';
			if (!alpha[idx])
			{
				alpha[idx] = true;
				algo(x + posX[i], y + posY[i], step + 1, alpha);
				alpha[idx] = false;
			}
		}
	}
}

int main()
{
	cin >> row >> col;

	cin.ignore();
	for (int i = 0; i < row; i++)
		cin >> map[i];

	bool alpha[26];
	fill_n(alpha, 26, false);

	algo(0, 0, 1, alpha);

	cout << mMax;

	return 0;
}

2019-01-01 15:57:20에 Tistory에서 작성되었습니다.