[leetcode][79] Word Search

문제 : https://leetcode.com/problems/word-search/

---

2차원 문자 배열, 단어가 주어지면 배열에 단어의 유무를 리턴하는 문제. 신문 단어 퍼즐 같은 문제.

 

DFS로 풀었다.

문자열 배열을 탐색하면서 탐색중인 인덱스를 시작 위치로 하여 단어가 있는지 판단한다.

// board: 2차원 문자 배열
// word : 찾는 단어
// board[x][y]를 시작 위치로 하여 word가 있는지
find(board, x, y, word):
	// 경계 체크
    if(x, y 이미 방문) return false
    if(board[x][y]와 word의 첫 번째 문자가 같지 않다면) return false
    ans = false
	x, y 방문 체크
    for(nx, ny = 상, 하, 좌, 우 이동한 좌표):
    	ans |= find(board, nx, ny, word[1..])
    return ans
    
main:
    for(i = 0..N):
        for(j = 0..M):
            ans |= find(board, i, j, word);

 수도코드는 위와 같다.

 

시간복잡도는 O(배열크기 ^ 2)인 것 같은 느낌적인 느낌.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/79.%20Word%20Search.cpp

---

DFS로 풀고나서 토론글에서 백트래킹 사용한 것과 사용안 한 코드의 시간차이를 보고 나도 한 번 돌려봤다.

 

/**
 * algorithm : DFS
 * Runtime : 916ms
 * Memory : 432.3 MB
 */
// board: 문자열 배열
bool find(vector<vector<char>> board, int x,int y, int wordInd) {
	if (wordInd >= word.size()) return true;
	if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) return false; 
	if (board[x][y] != word[wordInd]) return false;

	board[x][y] = ' '; // 방문 표시
	bool ans = false;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		ans |= find(board, nx, ny, wordInd+1);
		if (ans) break;
	}
	return ans;
}

/**
 * algorithm : DFS, Backtracking
 * Runtime : 20ms
 * Memory : 9.1 MB
 */
// board: 문자열 배열 참조
bool find(vector<vector<char>>& board, int x,int y, int wordInd) {
	// 생략

	char tmp = board[x][y]; // 현재 방문하고 있는 칸의 문자를 임시 저장
	board[x][y] = ' '; // 방문 여부 표시
	bool ans = false;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		ans |= find(board, nx, ny, wordInd+1);
		if (ans) break;
	}
	board[x][y] = tmp; // 방문 표시 제거. 문자 복원
	return ans;
}

풀링크는 소스코드 링크에서 확인가능하다.

큰 차이점은 재귀함수의 파라미터로 문자열 배열 값을 넘기냐 참조를 넘기냐의 차이다.

시간이랑 공간 차이가 backtracking이 현저히 높다.

dfs, backtracking 구현은 하면서 둘의 차이는 좀 애매하게 알고있었는데 이참에 좀 확실히 알게된 것 같다.