1987_알파벳 (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다.

 

1987_알파벳

 - 이 문제는 DFS를 활용하여 이미 거쳐간 알파벳인지 확인해주는 문제

 - 입력된 알파벳 배열로부터 DFS 탐색을 하며 이미 내가 사용한 알파벳인지, 내가 거쳐갔던 길인지를 확인하면서 풀이하면 된다.

 - 문제 풀이는 DFS와 백트래킹을 활용하여 풀이했다.

 - 자세한 내용은 코드의 주석을 참고하자.

 

	//백트래킹 형태로 접근하는 문제 ( 사실 DFS로 푸는 많은 문제들이 결과적으로 백트래킹 형태를 띈다고 생각한다 )
	// 1. 현재 접근 요소가 이전에 접근한 요소에 해당되는가
	// 2. 배열 범위를 넘어서는가
	#include <iostream>
	#include <string>
	using namespace std;
	//이미 접근한 알파벳인지 확인하기 위한 배열 선언 및 초기화
	bool exist_alphbet[26] = { 0 };
	//이미 접근한 위치인지 확인하기 위한 배열 선언 및 초기화
	bool check[20][20] = { 0 };
	//영문자 보드판을 위한 배열 선언 및 초기화
	char board[20][20] = { 0 };
	//다음 알파벳을 탐색하기 위한 방위행렬 선언 및 초기화 , 우 하 좌 상
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	//입력 알파벳 배열의 row, column 값을 가지는 변수 선언 및 초기화
	int R = 0, C = 0;
	//탐색 최대값을 가질 변수 선언 및 초기화
	int res = 0;
	//param x,y : 현재 위치 변수
	//param depth : 탐색 깊이 변수
	void dfs(int x, int y, int depth)
	{
	//보드판의 현재 위치 알파벳을 가져온다 ( 'A' -> 0 으로 가져와서 exist_alphbet을 알파벳순으로 접근하여 확인
	int cur_alphabet = board[y][x] - 'A';
	//해당 알파벳을 가져온 적이 있다면 반환
	if (exist_alphbet[cur_alphabet] == true)
	return;
	//해당 알파벳을 가져왔다고 표시
	exist_alphbet[cur_alphabet] = true;
	//현재 위치를 방문했음을 표시
	check[y][x] = true;
	//다음 탐색지를 정하기 위해 루프
	for (int i = 0; i < 4; i++)
	{
	//다음 탐색지 좌표를 가져온다
	int xn = x + dx[i];
	int yn = y + dy[i];
	//다음 위치가 탐색범위를 벗어나면 무시
	if (xn < 0 || xn >= C || yn < 0 || yn >= R) continue;
	//다음 위치를 탐색한 적이 없다면 탐색 호출
	if (check[yn][xn] == false)
	dfs(xn, yn, depth + 1);
	}
	//최종 depth값을 가져온다.
	//가장 깊게 들어간 값이 res에 저장된다
	if (res < depth)
	res = depth;
	//현재 위치에 대해 다음 탐색을 모두 마친 상태라면
	//현재 위치에 대한 알파벳 정보와 방문 정보를 모두 초기화한다
	exist_alphbet[cur_alphabet] = false;
	check[y][x] = false;
	}
	int main(void)
	{
	//보드판의 row와 column 값을 입력받는다
	cin >> R >> C;
	//보드판을 조회
	for (int row = 0; row < R; row++)
	{
	//보드판의 정보를 문자열 형태로 받아
	string tmp_row;
	cin >> tmp_row;
	//column에 해당하는 문자열 점보를 board 배열에 표시
	for (int column = 0; column < C; column++)
	{
	board[row][column] = tmp_row[column];
	}
	}
	//dfs탐색 시작 , 현재 위치를 카운트하고 시작하므로 depth값을 1로 시작
	dfs(0, 0, 1);
	//결과 출력
	cout << res << endl;
	return 0;
	}

view raw 1987_알파벳.cpp hosted with ❤ by GitHub