이번에는 백준 1987번 알파벳 문제를 풀어보았습니다.
문제를 처음 봤을 때 한 번 지나간 알파벳은 다시 방문할 수 없다는 조건이 있었기 때문에 DFS와 백트래킹을 이용하여 해결할 수 있다고 생각했습니다.
현재까지 지나온 알파벳들을 저장하면서 이동 가능한 모든 경우를 탐색하도록 구현하였습니다.
문제 설명
좌측 상단에서 말을 이동시킬 수 있습니다.
말은 상하좌우로 이동할 수 있으며, 지금까지 지나온 경로에서 한 번이라도 등장한 알파벳은 다시 방문할 수 없습니다.
말이 이동할 수 있는 최대 칸 수를 구하는 문제입니다.
풀이 아이디어
DFS를 이용하여 이동 가능한 모든 경로를 탐색하였습니다.
현재 위치를 방문 처리한 뒤, 현재 알파벳을 map에 저장하였습니다.
다음 위치로 이동할 때는 이미 방문한 칸인지 확인하고, 현재까지 등장한 알파벳인지도 함께 확인하였습니다.
더 이상 이동할 수 없는 경우 현재까지 이동한 칸 수로 최댓값을 갱신하였습니다.
DFS가 종료될 때는 방문 정보와 알파벳 정보를 다시 제거하여 다른 경로를 탐색할 수 있도록 백트래킹을 수행하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int inp[20][20], visited[20][20];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
map<int,int> ret;
int R,C;
int max_val = INT_MIN;
void dfs(int y, int x, int level) {
visited[y][x] = 1;
ret[inp[y][x]] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
if (visited[ny][nx]) continue;
if (ret.find(inp[ny][nx]) != ret.end()) continue;
dfs(ny, nx, level + 1);
}
visited[y][x] = 0;
ret.erase(inp[y][x]);
max_val = max(max_val, level);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> R >> C;
for (int i=0; i<R; i++) {
string s;
cin >> s;
for (int j=0; j<C; j++) {
inp[i][j] = s[j] - 'A';
}
}
ret[inp[0][0]] = 1;
dfs(0,0,1);
cout << max_val << '\n';
return 0;
}풀이 흐름
- 입력을 받아 보드의 알파벳을 저장합니다.
- 시작 위치
(0, 0)에서 DFS를 수행합니다. - 현재 위치를 방문 처리하고 현재 알파벳을 map에 저장합니다.
- 상하좌우를 탐색하면서 이동 가능한 위치를 확인합니다.
- 이미 방문한 칸이거나 같은 알파벳이라면 이동하지 않습니다.
- 이동 가능한 경우 DFS를 계속 수행합니다.
- 탐색이 끝나면 방문 정보와 알파벳 정보를 제거합니다.
- 현재 이동한 칸 수를 이용하여 최댓값을 갱신합니다.
구현 포인트
1. 방문한 알파벳 관리
현재까지 지나온 알파벳을 map으로 관리하였습니다.
map<int, int> ret;현재 위치를 방문하면 map에 추가하였습니다.
ret[inp[y][x]] = 1;2. 같은 알파벳 확인
다음 위치의 알파벳이 이미 등장했다면 이동하지 않았습니다.
if (ret.find(inp[ny][nx]) != ret.end()) continue;현재까지 지나온 경로에서 한 번이라도 등장한 알파벳은 다시 사용할 수 없기 때문입니다.
3. 방문한 칸 확인
이미 방문한 칸은 다시 탐색하지 않도록 처리하였습니다.
if (visited[ny][nx]) continue;현재 DFS 경로에서만 방문 여부를 관리하였습니다.
4. 백트래킹
DFS가 종료되면 방문 정보와 알파벳 정보를 다시 제거하였습니다.
visited[y][x] = 0;
ret.erase(inp[y][x]);이후 다른 경로를 탐색할 수 있도록 원래 상태로 복구하였습니다.
5. 최댓값 갱신
현재 위치에서 더 이상 이동할 수 없는 경우를 포함하여 DFS가 종료될 때마다 최댓값을 갱신하였습니다.
max_val = max(max_val, level);모든 경로를 탐색한 뒤 가장 큰 이동 칸 수를 정답으로 출력하였습니다.
