백준 1987번: 알파벳 - DFS, 백트래킹 C++

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

1987번: 알파벳

1.문제설명

2 4
CAAB
ADCB

다음과 같이 알파벳으로 이루어진 보드가 주어질 때

각 알파벳은 한 번씩만 방문할 수 있다.

좌측 상단(C)에서 시작해서 상하좌우로 이동하여

이동할 수 있는 최대 칸 수를 구해야한다.

 

 

백준 1987번 알파벳

백준 1987번 알파벳

D로 이동하면 D에서 상하좌우를 보면

위는 이미 방문해서 갈 수 없고 좌우는 이미 지난 알파벳이어서 방문할 수 없어서

D에서 깊이탐색이 끝나게 되고,

이동 거리는 3이다.

 

 

2.접근방법[알고리즘]

이 문제는 말이 최대한 몇칸을 움직일 수 있는지 구해야하는 문제다.

보통 DFS나 BFS로 최단거리를 많이 구하는데 이 문제는 다르게

이동할 수 있는 최대 거리를 구해야한다.

 

그리고 각 알파벳 마다 한번 씩만 방문할 수 있다.

방문한 알파벳을 저장해주면서 DFS 탐색을 돌아

최대 이동 거리를 갱신해주어야 한다.

 

 

2-1. 방문한 노드 좌표는 따로 저장을 안해주어도 되나?

방문한 알파벳을 저장해주면 알파벳 정보에

방문한 노드 정보까지 자연스럽게 포함된다

예를 들어 전에 방문한 노드가 C라면 C를 저장해주면

노드 번호를 따로 저장해주지 않아도 다음 노드가 C이면 탐색을 하지 않는다.

그러므로 방문한 알파벳만 저장하고 체크하면 된다.

 

 

2-2. DFS 코드

DFS(x좌표, y좌표, 이동거리) 이렇게 매개변수를 두고

dist가 최대일 때마다 갱신해주면서 깊이탐색 했다.

 

bool 배열 ch_alpha에 해당 알파벳이 이미 방문된 알파벳인지 체크해준다.

백트래킹을 돌면서 최대 이동거리를 갱신한다.

int r, c, ans;
char arr[21][21];
bool ch_alpha[26];

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

void DFS(int x, int y, int dist) {
	
	ans = max(ans, dist);

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
		
		int next_alpha = arr[nx][ny] - 'A';
		if (ch_alpha[next_alpha] == 0) {
			ch_alpha[next_alpha] = 1;
			DFS(nx, ny, dist + 1);
			ch_alpha[next_alpha] = 0;
		}
	}
}

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int r, c, ans;
char arr[21][21];
bool ch_alpha[26];

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

void DFS(int x, int y, int dist) {
	
	ans = max(ans, dist);

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
		
		int next_alpha = arr[nx][ny] - 'A';
		if (ch_alpha[next_alpha] == 0) {
			ch_alpha[next_alpha] = 1;
			DFS(nx, ny, dist + 1);
			ch_alpha[next_alpha] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> r >> c;

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

	ch_alpha[arr[0][0] - 'A'] = 1;
	DFS(0, 0, 1);

	cout << ans << '\n';

}

백준 1987번 시간 및 메모리