[백준 알파벳] DFS, BackTracking 문제

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

1987번: 알파벳

 

배운점

1. 중복검사는 visited[i]로 하고, backtraking 해서 올라올 때, visited가 제대로 업데이트 되는지 확인.

2. 제출하기전 반례를 넣고, printf(cout)을 통해서 원하는 대로 작동하는지 우선 작동과정을 확인해볼 필요가 있다.

 

 

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

int visited[26];
char map[20][20];
int ret;
int R, C;
//char cur;	// 디버깅, 출력용 변수
//char path[20]; // 디버깅, 출력용 변수
void DFS(int depth, int i, int j)
{
	if(depth > ret)
		ret = depth;
/*
	cout << "현재경로";
	for (int i = 0; i < depth; i++)
	{
		cout << path[i];
	}
	cout << '\n';*/

	int alphabet;
	/// up, down, left, right DFS
	if (i > 0)	//up
	{
		//cur = map[i - 1][j];
		alphabet = map[i - 1][j] - 'A'; // 알파벳을 인덱스화(정수화)한다.
		//path[depth] = map[i - 1][j];
		if (!visited[alphabet])	//만약 방문 안했으면
		{
			visited[alphabet] = 1;
			DFS(depth + 1, i - 1, j);
			visited[alphabet] = 0;
		}
	}
	if (i+1 <= R-1)	//down
	{
		//cur = map[i + 1][j];
		alphabet = map[i + 1][j] - 'A'; // 알파벳을 인덱스화(정수화)한다.
		//path[depth] = map[i + 1][j];
		if (!visited[alphabet])	//만약 방문 안했으면
		{
			visited[alphabet] = 1;
			DFS(depth + 1, i + 1, j);
			visited[alphabet] = 0;
		}
	}

	if (j-1 >=  0)	//left
	{
		//cur = map[i][j - 1];
		alphabet = map[i][j-1] - 'A'; // 알파벳을 인덱스화(정수화)한다.
		//path[depth] = map[i][j - 1];
		if (!visited[alphabet])	//만약 방문 안했으면
		{
			visited[alphabet] = 1;
			DFS(depth + 1, i, j-1);
			visited[alphabet] = 0;
		}
	}

	if (j+1 <= C-1)	//right
	{
		//cur = map[i][j + 1];
		alphabet = map[i][j + 1] - 'A'; // 알파벳을 인덱스화(정수화)한다.
		//path[depth] = map[i][j + 1];
		if (!visited[alphabet])	//만약 방문 안했으면
		{
			visited[alphabet] = 1;
			DFS(depth + 1, i, j+1);
			visited[alphabet] = 0;
		}
	}
}

int main()
{
	// R,C 입력받고
	cin >> R >> C;
	
	string str[20];
	for (int i = 0; i < R; i++)
	{
		cin >> str[i];
	}
	// str으로 받은거 map으로 옮기기
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			map[i][j] = str[i][j];
		}
	}
	// 초기위치 방문표시
	int alphabet = map[0][0] - 'A';
	visited[alphabet] = 1;
	//path[0] = map[0][0];
	
	// 초기 depth 는 1 로 집어넣어야한다.(문제조건)
	DFS(1, 0, 0);	// input : depth, i ,j
	
	cout << ret;

	return 0;
}