[백준 1987][💛4] 알파벳 (DFS, 백트래킹)

🚀 난이도

💛 골드 4

🚀 문제

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

🚀 내 풀이 ⭕

뭔가 생김새는 BFS 문제 같았지만.. 문제를 읽어보니 백트래킹으로 풀어야 하는 문제였다. 왜냐하면 현재까지 선택해 온 경로에서 한번 방문 했었던 종류의 알파벳은 사용할 수 가 없기 때문이다. 즉, 현재까지 “선택해 온 알파벳”들의 정보가 필요하다. N-Queen 문제와 유사하다. BFS 는 너비 우선 탐색을 하기 때문에 이렇게 “선택해 온 경로”의 정보를 담기는 힘들다.

#include <bits/stdc++.h>

using namespace std;

int R, C, answer;
int dr[4] = { -1, 1, 0 , 0 };
int dc[4] = { 0, 0, -1 , 1 };
char board[20][20];
bool visited[26]; // 알파벳 별 방문 체크 (현재의 경로 기준이므로 성공이든 실패든 재귀 함수가 호출을 끝내고 돌아오면 다시 false 로 바꿔 방문 체크를 해제해준다.)

void dfs(int r, int c, int dist) {
	
	bool canGo = false;
	for (int i = 0; i < 4; ++i) {
		int nextR = r + dr[i];
		int nextC = c + dc[i];

		if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) continue; // 갈 수 없는 곳 1 (보드 범위를 넘어섬)
		char nextAlpha = board[nextR][nextC];
		if (visited[nextAlpha - 'A']) continue; // 갈 수 없는 곳 2 (현재의 경로 내에서 이전에 방문했었던 알파벳)

		canGo = true; // 갈 수 있는 곳 하나라도 발견했다면 true
		visited[nextAlpha - 'A'] = true;
		dfs(nextR, nextC, dist + 1);
		visited[nextAlpha - 'A'] = false; // ⭐ 또 다른 경로에서 해당 알파벳이 다시 선택될 수 있도록
	}

	if (!canGo) { // 더 이상 갈 수 있는 곳이 없다면! (즉, for문에서 재귀 한번도 못 돌림. 더 이상 나아갈 경로가 없음)
		answer = max(answer, dist);
		return;
	}
}

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

	cin >> R >> C;
	for (int i = 0; i < R; ++i)
		for (int j = 0; j < C; ++j)
			cin >> board[i][j];

	char nextAlpha = board[0][0];
	visited[nextAlpha - 'A'] = true; // 출발 지점 체크
	dfs(0, 0, 1); // 문제에서 시작점도 카운팅에 포함된다고 했으므로 1 에서 시작
	
	cout << answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기