BOJ 1987. 알파벳

🙇‍♀️[Gold IV] 알파벳 - 1987

문제 링크

성능 요약

메모리: 2028 KB, 시간: 1624 ms

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 1월 17일 10:31:40

문제 설명

세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 $R$과 $C$가 빈칸을 사이에 두고 주어진다. ($1\le R,C\le 20$) 둘째 줄부터 $R$개의 줄에 걸쳐서 보드에 적혀 있는 $C$개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

🚀풀이

DFS문제로 백트래킹을 해야한다.

처음에 BFS로 접근했다가 안풀려서 다시 했다.

char를 기록하는 배열을 만들어서 새로 추가할 알파벳이 기존에 등록되어 있는지 확인하면서 DFS를 돌려야한다.

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int seqSize = 1;
void DFS(pair<int, int> here)
{
	ch[seqSize++] = board[here.first][here.second];
	res = max(res, seqSize);

    // 기록된 ch 확인용
	//cout << endl;
	//cout << "현재 ch 상태 " << endl;
	//for (int i = 1; i <= seqSize; ++i)
	//{
	//	cout << ch[i] << " ";
	//}
	//cout << endl;

	for (int i = 0; i < 4; ++i)
	{
		int ny = here.first + dy[i];
		int nx = here.second + dx[i];

		if (ny < 1 || nx < 1 || ny > r || nx > c)
			continue;
		if (visited[ny][nx] == 1)
			continue;
		bool flag = false;
		for (int j = 1; j <= seqSize; ++j)
		{
			if (ch[j] == board[ny][nx])
			{
				flag = true;
				break;
			}
		}
		if (flag == true)
			continue;

		visited[ny][nx] = 1;
		DFS({ ny, nx });
		visited[ny][nx] = 0;
		ch[--seqSize] = ' ';
	}
}

예를 들어 아래와 같은 입력이 들어오면

2 4
CAAB
ADCB

아래와 같은 결과를 보인다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int r, c, res = 0;
char ch[500];
vector<vector<char>> board;
vector<vector<int>> visited;
void setting()
{
	cin >> r >> c;
	board = vector<vector<char>>(r + 1, vector<char>(c + 1));
	visited = vector<vector<int>>(r + 1, vector<int>(c + 1));

	string str;
	for (int i = 1; i <= r; ++i)
	{
		cin >> str;
		for (int j = 0; j < str.size(); ++j)
		{
			board[i][j + 1] = str[j];
		}
	}
}

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int seqSize = 1;
void DFS(pair<int, int> here)
{
	ch[seqSize++] = board[here.first][here.second];
	res = max(res, seqSize);

	//cout << endl;
	//cout << "현재 ch 상태 " << endl;
	//for (int i = 1; i <= seqSize; ++i)
	//{
	//	cout << ch[i] << " ";
	//}
	//cout << endl;

	for (int i = 0; i < 4; ++i)
	{
		int ny = here.first + dy[i];
		int nx = here.second + dx[i];

		if (ny < 1 || nx < 1 || ny > r || nx > c)
			continue;
		if (visited[ny][nx] == 1)
			continue;
		bool flag = false;
		for (int j = 1; j <= seqSize; ++j)
		{
			if (ch[j] == board[ny][nx])
			{
				flag = true;
				break;
			}
		}
		if (flag == true)
			continue;

		visited[ny][nx] = 1;
		DFS({ ny, nx });
		visited[ny][nx] = 0;
		ch[--seqSize] = ' ';
	}
}

void solve()
{
	DFS({ 1, 1 });
	cout << res - 1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}