[백준 알고리즘]/[C++]
1987번 알파벳 | DFS | 백준 5014 C++ 코드
말하는펭귄
2021. 3. 9. 10:32
728x90
반응형
이번 포스팅은 백준 1987번 알파벳입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
기본 알고리즘
DFS 깊이 우선 탐색
백트래킹
전체 코드
|
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
|
//백준1987 알파벳
#include <iostream>
using namespace std;
int R, C;
const int MAX = 21;
char map[MAX][MAX];
bool alphabet[26];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
int ans;
int max(int i, int j) {
if (i > j)
return i;
else
return j;
}
void DFS(int y, int x, int cnt) {
ans = max(ans, cnt);
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C)
continue;
if (alphabet[map[ny][nx]-'A']==false) {
alphabet[map[ny][nx] - 'A'] = true;
DFS(ny, nx, cnt + 1);
alphabet[map[ny][nx] - 'A'] = false;
}
}
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> map[i][j];
}
}
alphabet[map[0][0] - 'A'] = true;
DFS(0, 0, 1);
cout << ans;
}
|
cs |
728x90
반응형