[백준/C++] 1987번. 알파벳

[백준] 1987번. 알파벳

1. 문제

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

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

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

2. 입력

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

3. 출력

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

4. 풀이

• DFS 문제
• DFS를 하면서 방문한 칸의 알파벳과 같은 알파벳에 방문한 적이 있는지도 확인해야 한다.
  2개의 visited가 필요하다.
• 그 외에는 다른 DFS 문제와 비슷하다.

5. 처음 코드와 달라진 점

• DFS를 다 만들어놓고 visited를 나중에 추가해서 처음 시작점에 방문 처리와 알파벳 방문 처리를 해주지 않아서 수정했다.
• DFS 할 때 len을 answer에 바로 넣었는데 더 작은 값이 들어갈 수도 있어서 answer = max(len, answer)로 바꾸어 주었다.

💡 추가수정

• visited[nx][ny] = true; 구문 삭제
  방문 처리를 하는 과정에서 중복되는 코드가 있어서 수정

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

char board[20][20];
bool visited[20][20] = {0, };
bool alphabet[26] = {0, };

int r, c;
int answer;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void dfs(int x, int y, int len) {
  answer = max(len, answer);

  visited[x][y] = true;
  alphabet[board[x][y] - 'A'] = true;

  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;
    if(visited[nx][ny] || alphabet[board[nx][ny] - 'A']) continue;

    alphabet[board[nx][ny] - 'A'] = true;

    dfs(nx,ny, len+1);

    visited[nx][ny] = false;
    alphabet[board[nx][ny] - 'A'] = false;

  }
}

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  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<<answer;
}