[#99][알고리즘][백준] 1987. 알파벳
[백준] 1987. 알파벳
문제 링크(https://www.acmicpc.net/problem/1987)문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
예제 입력 1
2 4 CAAB ADCB
예제 출력 1
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>
#include <algorithm>
using namespace std;
char arr[21][21];
bool alpha[26] = { false };
int tx[] = { 1,0,0,-1 };
int ty[] = { 0,1,-1,0 };
int R, C, maxvalue = 1;
void dfs(int x, int y, int mv) {
//최대로 갈 수 있는 칸 수
if (mv > maxvalue) maxvalue = mv;
for (int i = 0; i < 4; i++) {
int nx = x + tx[i];
int ny = y + ty[i];
//배열 인덱스를 초과하지 않으며, 밟지 않은 알파벳을 탐색
if (nx >= 0 && nx < R && ny >= 0 && ny < C && (alpha[arr[nx][ny]-65]==0)) {
alpha[arr[nx][ny] - 65] = true;
dfs(nx, ny, mv+1);
//백트래킹 위해서
alpha[arr[nx][ny] - 65] = false;
}
}
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
cin >> arr[i][j];
maxvalue = 1;
//그 알파벳을 이미 밟았다.
alpha[arr[0][0] - 65] = true;
dfs(0,0, maxvalue);
cout << maxvalue << endl;
return 0;
}
| cs |
댓글
댓글 쓰기