[BAEKJOON] 1987 알파벳 (C++)

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

1987번: 알파벳

문제

 

풀이

가려는 칸이 이미 밟았던 알파벳인지 확인하며 지날 수 있는 최대 칸 수를 구해야 한다.

밟았던 알파벳인지에 대한 기록을 유지한다. 최대 길이를 구한다.

-> DFS임을 알 수 있다.

 

check 배열을 이용해 check[알파벳-'A']로 방문 여부를 체크했다.

일반적인 dfs방식이지만 이미 방문한 알파벳인 칸은 방문할 수 없다.

방문가능하다면 해당 문자칸을 방문했다는 체크를 check배열에 해주고 방문한다.

방문을 마쳤다면 다시 check를 해제해준다.

여기서 방문을 마쳤다는 의미는 해당 칸에서 가능한 부분을 모두 탐색한 경우이다.

 

코드

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

#define endl "\n"

using namespace std;

int R,C, ans;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool check[26];
char MAP[21][21];
void Input() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> MAP[i][j];
		}
	}
}

void dfs(int y, int x, int cnt) {
	int xx, yy;
	ans = max(ans, cnt);
	
	for (int i = 0; i < 4; i++) {
		xx = x + dx[i]; yy = y + dy[i];
		if (xx<0 || xx>=C || yy<0 || yy>=R) continue;
		if (check[MAP[yy][xx]-'A'] == 0) {
			check[MAP[yy][xx] - 'A'] = 1;
			dfs(yy, xx, cnt + 1);
			check[MAP[yy][xx] - 'A'] = 0;
		}
	}
}

void Solve() {

	check[MAP[0][0]- 'A'] = 1;
	dfs(0, 0, 1);

	cout << ans;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();
	return 0;
}