삼성 7699. 수지의 수지 맞는 여행

7699. 수지의 수지 맞는 여행

링크

난이도 : d4
정답률 : _51%

설계

자료구조

이미 방문한 알파벳은 방분하지 않으므로 visited['Z' - 'A'] 를 만들어 사용한다.

backtracking

이미 정답의 max를 구한 경우, 더이상 탐색하지 않아도 된다.

가능한 max의 경우는 입력된 지도의 알파벳 종류 + 1이다.

따라서 dfs 함수에 다음 코드를 추가해준다

if (answer > MAX) {
  return;
}

정리

내 코드	빠른 코드
18 ms	18 ms

내 코드가 제일 빠른 코드이다.

고생한 점

처음에 BFS로 풀려고 한 경우 계속 시간초과가 발생했다.

DFS로 바꾼 뒤 완전탐색을 수행했을 때 약 3초정도의 시간이 걸렸다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

struct axis {
  int y, x;
};

axis moves[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[20][20];
int answer, R, C, MAX;
bool visited['Z' - 'A'];

void clear() {
  for (int i = 0; i < 'Z' - 'A'; i++) {
    visited[i] = 0;
  }
  answer = 1, MAX = 0;
}

void dfs(axis current, int count) {
  answer = max(answer, count);

  if (answer > MAX) {
    return;
  }

  visited[map[current.y][current.x] - 'A'] = 1;

  for (int dir = 0; dir < 4; dir++) {
    axis next = current;
    next.x += moves[dir].x;
    next.y += moves[dir].y;

    if (next.y < 0 || next.y >= R || next.x < 0 || next.x >= C ||
        visited[map[next.y][next.x] - 'A']) {
      continue;
    }

    dfs(next, count + 1);
  }

  visited[map[current.y][current.x] - 'A'] = 0;
}

void solution(int test_case) {
  clear();
  cin >> R >> C;

  bool alphabets['Z' - 'A'] = {
      0,
  };

  for (int y = 0; y < R; y++) {
    for (int x = 0; x < C; x++) {
      cin >> map[y][x];
      alphabets[map[y][x] - 'A'] = 1;
    }
  }

  for (bool b : alphabets) {
    b ? MAX += 1 : MAX;
  }

  dfs(axis{0, 0}, 1);

  cout << "#" << test_case << " " << answer << "\n";
}

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

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}