LeetCode - 79. Word Search (C++)

Medium, DFS

RunTime : 254 ms / Memory : 9.99 MB

문제

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

풀이

• dfs시에 파라미터가 많은 것을 선호하지 않아서 필요 변수들을 Class의 멤버변수로 선언했다.
• 이후에 dfs를 수행하면서 현재 위치가 target[idx]와 일치하는지 확인하고,
  다르면 false
• idx값이 target길이의 끝까지 왔다면 다 맞은것이므로 true 리턴

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

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int n, m;
    vector<vector<int>> visited;
    vector<vector<char>> board;
    string target;

    bool dfs(int x, int y, int idx) {
        if (board[x][y] != target[idx]) return false;
        if (idx == target.size() - 1) return true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] == 0) {
            	visited[x][y] = 1;
                if (dfs(nx, ny, idx + 1)) {
                    return true;
                }
                visited[x][y] = 0;
            }
        }
        return false;
    }

    bool exist(vector<vector<char>>& inputBoard, string word) {
        board = inputBoard; // 입력을 멤버 변수로
        target = word;
        n = board.size();
        m = board[0].size();
        visited = vector<vector<int>>(n, vector<int>(m, 0));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word[0]) {
                    if (dfs(i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

C++ DFS에서 파라미터를 어떻게 두는게 효율적인지 잘 모르겠다.
어차피 넘겨줄 때 &참조로 넘겨줘서 스택메모리 효율성은 비슷한데...
코드 가독성을 생각하면 파라미터로 이것저것 넘겨주는거보다 전역(Class 멤버변수)로 선언하는게 좋은거 같기도 하고...