문제에서 요구하는 것은 (0,0) 인덱스에서 시작해서 한 칸씩 상하좌우로 이동할 때,
중복된 알파벳을 피해서 최대한 이동 가능한 횟수를 찾는 것입니다.
이전에 했던 토마토처럼 탐색형 문제이면서 DFS를 이용하는 문제입니다.
( BFS도 가능할 겁니다.)
문제 핵심 IDEA
알파벳 문제는 경로 탐색형 문제입니다. 해결 방법은 크게 DFS, BFS 두 가지가 있습니다.
확인해줘야 하는 것은 알파벳의 중복성, 이미 확인한 경로인가?입니다.
그리고 이전 값으로 돌아올 경우 이전에 지난 데이터는 원상 복구시켜줘야 합니다.
생각흐름
기초 흐름
문제를 보자마자 DFS로 풀이를 잡았습니다.
신경 써줘야 하는 조건은 다음과 같습니다.
[ 조건 ]
2. 방문한 곳인가? -> B, DFS에서 기본인 bool visit array로 처리합니다.
첫번째 접근
- 처음에는 간단하게 생각해서 단순 DFS로 풀려고 했습니다. 하지만 문제가 발생한 것은 이미 지나온 경로와 데이터를 처리할 수 없었습니다. 예를 들어, 하나의 경로에서 뻗어나가는 4가지 경우의 수(상, 하, 좌, 우) 중에 2번째(하 이동)에 들어간 DFS가 끝났다고 해서 그 값이 최대라는 보장이 없습니다. 이후 3번째(좌 이동), 4번째(우 이동) DFS에서 더 많은 이동이 나올 수도 있기 때문입니다.
두번째 접근
- 그래서 중복을 없애면서 모든 경우를 다 확인하는 형식의 DFS를 진행해야겠다고 생각을 했습니다. 이와 같은 연습하기 가장 좋은 게 N과 M 시리즈입니다. DFS를 빠져나온 뒤 진행되는 코드에 해당 인덱스의 알파벳과 방문을 false로 바꿔주고, 경로를 -1 해주는 것입니다. 즉, 내가 처리한 경로를 없던 셈 치고 진행을 하겠다는 겁니다. 그 후 그냥 if문 조건이 넘어가면 max값 비교를 하게 짰더니 문제가 발생하더군요. 그냥 조건이 안 맞으면 무조건 max값을 처리해 버리지 뭡니까…
세번째 접근
- 해결 방법은 단순했습니다. 상하좌우 어디로도 이동이 불가능하면 그때 max를 처리해주면 됩니다. 즉 이동 반복문의 iterator가 최댓값 3에 도달한 경우, max 비교를 해주면 됩니다.
정답 코드
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
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
using namespace std;
int dirx[4] = {-1, 0, 0, 1};
int diry[4] = {0, -1, 1, 0};
int R, C;
int cnt;
int result = -1;
char map[20][20];
bool visit[20][20];
bool alphabet[26]; // A = 0 ~ Z = 25
void dfs(int x, int y) {
visit[x][y] = true;
cnt++;
for (int i = 0; i < 4; i++) {
int nx = x + dirx[i];
int ny = y + diry[i];
if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
if (!visit[nx][ny]) {
char next_alphabet = map[nx][ny];
if (!alphabet[next_alphabet - 'A']) {
alphabet[next_alphabet - 'A'] = true;
dfs(nx, ny);
alphabet[next_alphabet - 'A'] = false;
visit[nx][ny] = false;
cnt--;
}
}
}
if (i == 3)
result = max(cnt, result);
}
}
int main() {
string input;
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> input;
for (int j = 0; j < C; j++) {
map[i][j] = input[j];
}
}
alphabet[map[0][0] - 'A'] = true;
dfs(0, 0);
cout << result << "\n";
}
좀 깔끔하게 풀은 거 같네요.
삼성 A형을 따기 위해서 요즘 B, DFS 위주의 공부를 하는 중인데 익숙지가 않습니다…;;
GitHub - https://github.com/cow-coding/algorithm/blob/master/BOJ/C%2B%2B/1987.cpp
Comments powered by Disqus.