[BOJ] 1987 - 알파벳

https://www.acmicpc.net/problem/1987

BOJ - 알파벳

문제 유형: 백트래킹, dfs, 비트마스킹

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 256MB

 

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1≤R,C≤20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

풀이

알파벳의 방문 여부를 int에 비트로 표시한다.

4비트 기준으로 예시를 보자.

1100이면 'D'와 'C'를 방문했다는 의미이다.

0001이면 'A'를 방문했다는 의미이다.

 

1, 1부터 시작해서  인접한 타일들 중에서 방문한적 없는 알파벳으로 백트래킹한다.

즉, 방문처리 후 재귀호출 후 최대 칸수를 갱신하고, 방문처리를 해제한다.

 

최종적으로 최대값을 반환한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int r, c;
char board[21][21];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int solve(int x, int y, int &visited) {
  int res = 0;
  for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if (nx < 0 || nx >= r || ny < 0 || ny >= c)
      continue;

    int ch = board[nx][ny] - 'A';
    if ((visited & (1 << ch)) == 0) {
      visited |= (1 << ch);
      res = max(res, 1 + solve(nx, ny, visited));
      visited &= ~(1 << ch);
    }
  }

  return res;
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> r >> c;
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      cin >> board[i][j];
    }
  }

  int visited = 0;
  visited |= (1 << (board[0][0] - 'A'));
  cout << solve(0, 0, visited) + 1 << "\n";

  return 0;
}