(cpp) Baekjoon 1987번 문제 ‘알파벳’ - 그래프이론, 그래프탐색, DFS, 백트래킹
Baekjoon 1987번 문제 ‘알파벳’ - 그래프이론, 그래프탐색, DFS, 백트래킹
문제풀이
행과 열의 크기를 입력받아 board에 r x c의 형태로 값을 저장한다. 시작 위치는 (0,0)으로 고정이고, 그 위치에 있는 알파벳을 방문 체크한다. check_board에 지나온 알파벳을 하나씩 넣기보다, A~Z 크기의 체크보드 bool형으로 만들고 방문시 true, 미방문시 false를 입력하는 방식이다. 처음으로 돌아와서, ‘A’를 빼주면 해당 알파벳이 ‘A’로부터 얼마나 떨어졌는지 알 수 있으므로 ‘A’뺀 숫자를 위치로 삼고(char A=65, B=66, C=67 ..이므로 A=0,B=1,C=2..로 바꾼 셈) 그 위치의 알파벳을 방문 체크(true)해주고 dfs시작한다.
시작 위치를 1로 카운트하면서 그 위치의 주변을 살펴 갈 수 있는 곳을 탐색한다. 다음 위치에 있는 알파벳이 방문한 적 없는 곳이면 해당 위치로 이동하면서 체크보드에 체크하고 그 위치부터 다시 dfs를 호출한다. 이때, dfs를 호출하는 횟수를 카운트하면 몇 칸 이동하는지 알 수 있다. 중요한 것은, dfs호출 후에, 그 위치의 체크보드를 비워주어야 한다는 것이다. 이는, 왼,오,위,아 네 개의 후보군을 탐색할 때, 왼쪽에 ‘F’가 있다고 해도 이와는 별개로 오른쪽에 있는 ‘F’에도 갈 수 있음을 의미한다.
코드
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int ans;
int r, c;
string al;
char board[20][20];
bool check_board[26]; //A~Z
int r_pos[4] = { -1,1,0,0 };
int c_pos[4] = { 0,0,1,-1 };
void dfs(int cur_r, int cur_c, int cnt)
{
ans = max(ans, cnt);
for (int i = 0; i < 4; i++)
{
int next_r = cur_r + r_pos[i];
int next_c = cur_c + c_pos[i];
if (next_r >= 0 && next_c >= 0 && next_r < r && next_c < c)
{
if (check_board[board[next_r][next_c] - 'A'] == false) //'A'빼는 이유는 해당 알파벳의 위치를 구하기 위함(char 'A' = 65이므로 빼주면 B는 1, C는 2...)
{
check_board[board[next_r][next_c] - 'A'] = true;
dfs(next_r, next_c, cnt + 1);
check_board[board[next_r][next_c] - 'A'] = false;
}
}
}
}
int main()
{
cin >> r;
cin >> c;
for (int i = 0; i < r; i++) {
cin >> al;
for (int j = 0; j < c; j++) {
board[i][j] = al[j];
}
}
check_board[board[0][0] - 'A'] = true;
dfs(0, 0, 1);
cout << ans << "\n";
}
- 공백없이 입력되는 n x m행렬로 2차원 배열로 저장하는 입력 방식이 필요함.
- 백트래킹(해당 경로가 해가 되지 않을 것 같으면 이전 노드로 돌아가서 다시 탐색하는 방법)을 사용해야 함.
- 왼,오,위,아 4개의 후보군 끼리는 같은 알파벳을 가질 수 있다.
- check_board를 map<char,bool>로 설정해서 ‘A’위치를 굳이 빼지 않도록 코드를 짜서 실행해 보았는데 시간이 거의 3배 더 든다. 정답은 맞음.