[BOJ/C++] 1987 알파벳 : DFS

문제

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

풀이

항상 map은 BFS로 풀고, 그래프 최단경로는 DFS로 풀었는데 map을 DFS로 푸는 것에 익숙해지자

이 문제는 2가지 포인트만 신경 쓰면 전형적인 그래프 탐색으로 쉽게 풀이 가능하다.

1. visited 배열을 2차원 배열이 아니라, 알파벳 26개 1차원 배열로 선언

2. (1,1) -> (2,1) -> (3,1)에서 (1,1) -> (2,1) -> (2,2)로 갈 때는 (3,1)을 다시 visited false 처리해줘야하므로 재귀 dfs 밑에 줄에 visited를 다시 false로 바꾸는 코드 추가해주기

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
char arr[21][21];
bool visited[26];
int ans = 0;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void dfs(int x, int y, int cnt) {
	int index = arr[x][y] - 'A';
	visited[index] = true;
	ans = max(ans, cnt);

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
			int index2 = arr[nx][ny] - 'A';
			if (!visited[index2]) {
				visited[index2] = true;
				dfs(nx, ny, cnt + 1);
				visited[index2] = false; //⭐⭐⭐⭐⭐⭐⭐
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char c;
			cin >> c;
			arr[i][j] = c;
		}
	}

	dfs(0, 0, 1);
	cout << ans;

	return 0;
}