[백준] 1987 알파벳 - C++

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

1987번: 알파벳

 

DFS 와 관련된 문제를 풀다가 알파벳 문제를 풀었다.

 

A~Z 가 26개라는 개념을 알면 쉽게 풀리는 문제였다.

 

골드 4 문제치고 쉬운 문제지만 시간복잡도 관련하여 정리하고 싶어 글을 작성한다. 

 

백준 내리막길 문제 (1520) 과 굉장히 유사한 문제이다. 내리막길 문제는 DFS 로 문제를 풀려다가 시간 초과의 장벽을 넘어서지 못했다.... 이 이유가 이 문제와 굉장히 유사한 것 같았다.  (내리막길 문제는 시간 복잡도가 O(4^500*500)이라서 단순 DFS로는 절대 못풀어서 혹시 알파벳 문제도 못푸나? 생각을 하였다. )

 

알파벳 문제의 시간 복잡도는 알파벳 26 개 이므로 O(4^26)이다. 얼핏보면 연산횟수 10억을 넘는 것 같지만 왔던 길은 가지 않고 지나갔던 알파벳은 안가도 되므로 사실상 4^26의 연산이 아니라서 시간 초과가 뜨지 않아서 DFS 로 풀어도 되는 듯 하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int graph[20][20];
bool visited[26];
int R, C;
int max_ans = 0;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };


void dfs(int x, int y, int count) {

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

		if (nx < 0 || ny < 0 || nx >= R || ny >= C|| visited[graph[nx][ny]]==true) {
			continue;
		}
		visited[graph[nx][ny]] = true;
		dfs(nx, ny, count + 1);
		visited[graph[nx][ny]] = false;
	}
}

int main() {
	
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < C; j++) {
			graph[i][j] = s[j] - 'A';
		}
	}

	visited[graph[0][0]] = true;
	dfs(0, 0, 1);

	cout << max_ans;
}