문제
1987: 알파벳
'추천 관련글,
수직 R 셀과 수평 C 셀이 있는 테이블 모양의 보드가 있습니다.
보드의 각 사각형에 대문자를 쓰고 왼쪽 상단 사각형(행 1 열 1)에 조각을 놓습니다.
위, 아래, 왼쪽 또는 오른쪽의 네 개의 인접한 사각형 중 하나에 조각이 배치됩니다.
www.acmicpc.net
설명
0, 0은 무조건 밟을 수만 있기 때문에 0을 true로 변경하고 DFS(0, 0, 1)로 함수를 시작합니다.
여기서 글자와 글자를 빼는 과정이 있는데 A가 지도상에 있었다면 65-65이므로 0번째 방문, B가 있으면 66-65이므로 1번째 방문알파벳은 이렇게 되어있다.
저장되었습니다.
이 문제의 핵심은 역추적(backtracking)이라는 DFS 함수의 실행 하에서 다시 방문한 배열을 잘못 만드는 부분이다.
나는 대부분의 그래프 문제가 유사한 코드 구조를 가지고 있어서 많은 문제를 접할 수 있다는 점이 좋습니다.
#include <iostream>
using namespace std;
int R, C, answer;
char map(20)(20);
bool visited(26);
void DFS(int x, int y, int count) {
answer = max(answer, count);
int dx() = { 0, 0, 1, -1 };
int dy() = { 1, -1, 0, 0 };
for (int i = 0; i < 4; i++) {
int nx = x + dx(i);
int ny = y + dy(i);
if (nx < R && ny < C && nx >= 0 && ny >= 0) {
if (visited(map(nx)(ny) - 'A') == false) {
visited(map(nx)(ny) - 'A') = true;
DFS(nx, ny, count + 1);
visited(map(nx)(ny) - '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);
}
}
visited(map(0)(0) - 'A') = true;
DFS(0, 0, 1);
cout << answer;
return 0;
}