[백준 알고리즘] 1987번: 알파벳
March 12, 2021
https://www.acmicpc.net/problem/1987
문제
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
풀이
문제에서 주어진 조건대로 4방향을 확인하면서 갈 수 있는 데까지 다 가보는 문제였다. DFS를 이용해서 이동횟수를 확인했는데, 이미 경로에서 사용했던 알파벳인지 확인하기 위해서 알파벳을 저장할 수 있는 배열을 하나 만들고 방문할 때마다. 이미 사용한 알파벳으로 체크해주었다. 알파벳은 해당 문자에 65를 빼면 0에서 부터 인덱싱이 가능하기 때문에 매번 65를 빼서 길이 26의 배열로 해결할 수 있도록 했다.
이 문제는 정점 방문여부를 배열이 따로 필요가 없었는데, 이미 방문했던 정점은 항상 사용한 알파벳으로 체크가 되기 때문에 사용한 알파벳을 확인하는 것으로 방문정점의 체크가 가능하다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 21;
int R, C;
bool alphaUsed[26];
char board[MAX][MAX];
int maxMove = 0;
bool isMovePossible (int r, int c){
return (r >= 0 && r < R) && (c >= 0 && c < C);
}
void dfs(int row, int col, int move){
alphaUsed[board[row][col] - 65] = true;
int rowDir [] = {1, -1, 0, 0};
int colDir [] = {0, 0, -1, 1};
for (int i = 0 ; i < 4 ; i++){
int nextRow = row + rowDir[i];
int nextCol = col + colDir[i];
if(isMovePossible(nextRow, nextCol) && !alphaUsed[board[nextRow][nextCol] - 65]){
dfs(nextRow, nextCol, move + 1);
}
}
alphaUsed[board[row][col] - 65] = false;
maxMove = max(maxMove, move);
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> R >> C;
for (int i = 0 ; i < R ; i++){
for (int j = 0 ; j < C ; j++){
cin >> board[i][j];
}
}
dfs(0, 0, 1);
cout << maxMove;
}
