[백준 C++] 1987번: 알파벳

1. 문제

 

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

1987번: 알파벳

 

2. 알고리즘 분류

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

 

3. 소스 코드

#include <iostream>
#include <string>

using namespace std;

int R, C;
int max_count; // 지나간 최대의 칸 수
int alphabet_table[26]; // 각 알파벳 카운팅용 테이블
char map[20][20]; // 보드 정보

// 방향 배열(상,하,좌,우)
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

// DFS 알고리즘(깊이 우선 탐색)
void dfs(int y, int x, int count)
{
	// 상,하,좌,우 이동
	for (int i = 0; i < 4; i++)
	{
		// 다음으로 이동할 위치
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue; // 보드를 벗어난 경우, 스킵
		if (alphabet_table[map[ny][nx] - 'A'] == 1) continue; // 이미 지나간 알파벳일 경우, 스킵

		alphabet_table[map[ny][nx] - 'A'] = 1; // 알파벳 기록
		max_count = max(max_count, count + 1); // 최대의 칸 갯수 갱신
		dfs(ny, nx, count + 1); // 다음 위치로 이동

		alphabet_table[map[ny][nx] - 'A'] = 0; // 기록한 알파벳 정보 리셋
	}
}

int main()
{
	// 보드 행과 열의 수 입력
	cin >> R >> C;

	// 보드에 들어갈 대문자 알파벳 입력
	for (int y = 0; y < R; y++)
	{
		string input_map;
		cin >> input_map;

		for (int x = 0; x < C; x++)
			map[y][x] = input_map[x];
	}

	alphabet_table[map[0][0] - 'A'] = 1; // 시작점의 알파벳 기록
	max_count = 1;  // 좌측 상단의 칸 포함
	dfs(0, 0, 1); // BFS 알고리즘을 통한 탐색

	// 말이 지날 수 있는 최대의 칸 수 출력
	cout << max_count;

	return 0;
}

 

5. 유용한 문법 및 알고리즘

 1) DFS 알고리즘(깊이 우선 탐색)

int R, C;
int max_count; // 지나간 최대의 칸 수
int alphabet_table[26]; // 각 알파벳 카운팅용 테이블
char map[20][20]; // 보드 정보

// 방향 배열(상,하,좌,우)
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

// DFS 알고리즘(깊이 우선 탐색)
void dfs(int y, int x, int count)
{
	// 상,하,좌,우 이동
	for (int i = 0; i < 4; i++)
	{
		// 다음으로 이동할 위치
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue; // 보드를 벗어난 경우, 스킵
		if (alphabet_table[map[ny][nx] - 'A'] == 1) continue; // 이미 지나간 알파벳일 경우, 스킵

		alphabet_table[map[ny][nx] - 'A'] = 1; // 알파벳 기록
		max_count = max(max_count, count + 1); // 최대의 칸 갯수 갱신
		dfs(ny, nx, count + 1); // 다음 위치로 이동

		alphabet_table[map[ny][nx] - 'A'] = 0; // 기록한 알파벳 정보 리셋
	}
}