인프런 커뮤니티 질문&답변

안녕하세요, 큰돌님. 강의 잘 듣고 있습니다.

DFS 재귀 vs. 반복문 구현 방법을 결정하는 기준에 대해 여쭙고 싶습니다.

제가 현재 고민중인 접근 방식은 다음과 같습니다:

1. 완전 탐색(완탐) 문제의 경우 일단 재귀로 구현

2. 엣지 케이스 테스트 시 메모리 초과(Memory Overflow) 또는 시간 초과(Time Overflow)가 발생하면 반복문으로 변경

코딩 테스트(코테)의 경우, 위와 같은 접근 방식이 적절할 지 조언을 부탁드리겠습니다.

재귀로 풀면 쉽게 풀리는 걸 알았지만 DFS를 반복문으로 구현하면 디버깅이나 메모리 측면에서 유리하다고 알고 있어, 이번 문제를 오기로 반복문으로 접근하여 풀고자 했습니다.

그러나 결과적으로 재귀로 작성한 코드보다 성능이 낮게 측정되었습니다. 여러 최적화 끝에 다음과 같은 코드를 작성했는데, 큰돌님께서 작성하신 코드보다 메모리를 4KB 더 소모하고, 실행 시간이 26ms 더 느리게 측정되었습니다.

테스트 케이스에 따라 제 코드가 더 빠르게 동작할 수도있겠지만 결과적으로, 어떤 문제는 반복문으로, 어떤 문제는 재귀로 풀어야 적절할지 를 어떻게 결정하지? 가 의문으로 남아 질문드립니다!

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

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

int R, C;
int grid[20][20];

inline bool is_valid(int y, int x) {
  return (0 <= y && y < R && 0 <= x && x < C);
}

int iterative_dfs() {
  stack<tuple<int, int, int, int>> st;

  int startMask = (1 << grid[0][0]);
  st.push({0, 0, 1, startMask});

  int maxDepth = 0;

  while (!st.empty()) {
    auto [y, x, depth, used] = st.top();
    st.pop();

    maxDepth = max(maxDepth, depth);

    for (int i = 0; i < 4; i++) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (!is_valid(ny, nx))
        continue;

      int alpha = grid[ny][nx];
      if (used & (1 << alpha))
        continue;

      int nextUsed = used | (1 << alpha);
      st.push({ny, nx, depth + 1, nextUsed});
    }
  }
  return maxDepth;
}

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

  cin >> R >> C;
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      char tmp_c;
      cin >> tmp_c;
      grid[i][j] = tmp_c - 'A';
    }
  }

  cout << iterative_dfs() << "\n";
  return 0;
}