https://www.acmicpc.net/problem/1987
1987번: 알파벳
문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는
www.acmicpc.net
처음 보드를 입력받을 때, 알파벳을 숫자로 변환해서 저장한다.
문자 - 'A'를 해줘서 A는 0, B는 1, C는 2 이런 식으로 저장된다.
방문한 알파벳에는 다시 갈 수 없으므로 방문 체크를 해주어야 한다.
A문자를 방문하면 check [0]에 true 체크, B를 방문하면 check [1]을 true 표시해주는 방식으로
방문 체크를 해나간다.
인접한 칸으로 이동할 수 있으면 이동할 좌표와 함께 이동 횟수(cnt) 값을 증가시켜서 함께 보내준다.
더 이상 갈 수 없는 경우 탐색을 멈추기 위해 z변수를 두고 다음 칸으로 이동할 수 없을 때마다 값을 증가시켜줬다.
z == 4 가 되면(인접한 상하좌우 네 칸으로 모두 갈 수 없으면) 이동한 횟수를 비교해주고 return 한다.
|
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <string>
using namespace std;
int r, c;
int ans;
bool check[26];
int map[20][20];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void solve(int x, int y, int cnt) {
int z = 0;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
z++;
continue;
}
if (check[map[nx][ny]]) {
z++;
continue;
}
check[map[nx][ny]] = true;
solve(nx, ny, cnt+1);
check[map[nx][ny]] = false;
}
//인접한 칸으로 더이상 이동할 수 없다.
if (z == 4) {
if (ans < cnt) ans = cnt;
return;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> r >> c;
for (int i = 0; i < r; i++) {
string s;
cin >> s;
for (int j = 0; j < c; j++) {
map[i][j] = s[j] - 'A';
}
}
check[map[0][0]] = true;
solve(0,0, 1);
cout << ans;
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 1182. 부분수열의 합 (0) | 2019.07.11 |
|---|---|
| [BOJ] 11723. 집합 (0) | 2019.07.11 |
| [BOJ] 7562. 나이트의 이동 (0) | 2019.07.09 |
| [BOJ] 2638. 치즈 (0) | 2019.07.08 |
| [BOJ] 2636. 치즈 (0) | 2019.07.08 |