https://www.acmicpc.net/problem/1987
문제
> 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
> 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
> 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
> 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
> 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.
> 말이 지나는 칸은 좌측 상단의 칸도 포함된다.접근
너비우선탐색을 하는데 백트래킹을 사용하여 탐색한다.
사방 탐색을 하여 새로 탐색할 곳이 범위 내라면 해당 좌표의 알파벳을 숫자로 변환해 이를 인덱스로 가지는 부울형 방문처리벡터에 검증을 해 탐색을 이어나간다.
문제해결
> R과 C를 입력받고 보드를 1,1 부터 R,C까지되게 생성한 후 입력받는다.
> 방문처리를 위한 used 부울형 벡터를 알파벳의 개수만큼 크기를 준다.
> 시작 위치가 1,1이고 이동 횟수가 0이므로 1,1,0을 넣고 Board 메소드를 호출한다.
> 시작칸도 지나는 칸에 포함되므로 이를 먼저 처리해준다.
해당 좌표의 알파벳에 접근해서 'A'를 빼주므로 이를 숫자로 변환한다. A는0, B는 1...로 바뀐다.
> 방문처리를 해주고 한칸 간것이므로 cnt를 누적한다.
> 사방탐색을 하며 새 좌표를 구한다. 범위내에 있는지 확인하고 있다면 이 좌표에 있는 알파벳을 또 변환하여 해당 알파벳을 밟은적이 있나 검증한다.
> 밟은적이 없다면 재귀로 그 위치로 들어간다. 이를 반복한다.
> 만약 사방탐색에서 가능한 경로가 없어 for문을 나오면 최대로 갈 수 있는 최대로 갔다는 뜻이므로 최대값을 갱신해준다.
> 그리고 이전 재귀로 돌아가서 다른 경로를 보기 위해 방문처리를 다시 false로 만들어 빠짐없이 탐색 되도록 한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int R, C;
vector<vector<char>> alpha;
vector<bool> used;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
int rst = 0;
void Board(int sr, int sc, int cnt)
{
used[alpha[sr][sc] - 'A'] = true;
cnt += 1;
for (int i = 0; i < 4; i++)
{
int nr = sr + dir[i];
int nc = sc + dic[i];
if (nr < 1 || nr > R) continue;
if (nc < 1 || nc > C) continue;
int idx = alpha[nr][nc] - 'A';
if (!used[idx])
{
Board(nr, nc, cnt);
}
}
rst = max(rst, cnt);
used[alpha[sr][sc] - 'A'] = false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> R >> C;
alpha.resize(R + 1, vector<char>(C+1));
used.assign(26, false);
for (int i = 1; i <= R; i++)
{
string str;
cin >> str;
for (int j = 1; j <= C; j++)
{
alpha[i][j] = str[j - 1];
}
}
Board(1, 1, 0);
cout << rst << '\n';
}
후기
알파벳을 숫자화 해서 인덱스하는것까지 잘 생각했다. 매번 소문자만 다뤘어서 0을 뻇는데 대문자는 A를 빼주면 된다.
