[백준 1987] 알파벳 (C#, C++) - soo:bak

문제 링크

1987번 - 알파벳

설명

보드의 좌상단에서 시작해 상하좌우로 이동하며, 같은 알파벳이 적힌 칸은 두 번 지날 수 없습니다. 최대 몇 칸을 지날 수 있는지 구하는 문제입니다.

접근법

먼저 DFS로 가능한 모든 경로를 탐색합니다. 각 칸에서 4방향으로 이동을 시도하고, 더 이상 갈 수 없으면 되돌아옵니다.

다음으로 이미 지나온 알파벳인지 빠르게 확인해야 합니다. 알파벳은 26개뿐이므로 비트마스크로 관리하면 확인과 되돌리기를 O(1)에 할 수 있습니다.

이후 탐색 중 도달한 최대 깊이를 갱신하며, 모든 탐색이 끝나면 그 값을 출력합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int R, C, best = 0;
    static char[,] board = new char[20, 20];
    static readonly int[] dr = { 0, 0, 1, -1 };
    static readonly int[] dc = { 1, -1, 0, 0 };

    static void Dfs(int r, int c, int depth, int mask) {
      best = Math.Max(best, depth);
      for (var d = 0; d < 4; d++) {
        var nr = r + dr[d];
        var nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= R || nc >= C)
          continue;
        var bit = 1 << (board[nr, nc] - 'A');
        if ((mask & bit) != 0)
          continue;
        Dfs(nr, nc, depth + 1, mask | bit);
      }
    }

    static void Main(string[] args) {
      var rc = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      R = rc[0];
      C = rc[1];
      for (var i = 0; i < R; i++) {
        var line = Console.ReadLine()!;
        for (var j = 0; j < C; j++)
          board[i, j] = line[j];
      }

      var startMask = 1 << (board[0, 0] - 'A');
      Dfs(0, 0, 1, startMask);
      Console.WriteLine(best);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int R, C, best = 0;
char board[20][21];
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

void dfs(int r, int c, int depth, int mask) {
  best = max(best, depth);
  for (int d = 0; d < 4; d++) {
    int nr = r + dr[d];
    int nc = c + dc[d];
    if (nr < 0 || nc < 0 || nr >= R || nc >= C)
      continue;
    int bit = 1 << (board[nr][nc] - 'A');
    if (mask & bit)
      continue;
    dfs(nr, nc, depth + 1, mask | bit);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> R >> C;
  for (int i = 0; i < R; i++)
    cin >> board[i];

  int startMask = 1 << (board[0][0] - 'A');
  dfs(0, 0, 1, startMask);
  cout << best << "\n";

  return 0;
}