[LeetCode] 79번 - Word Search [Swift]

문제 링크

Word Search - LeetCode

문제

Given an m x n board and a word, find if the 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.

 

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

 

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

 

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

 

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 200
• 1 <= word.length <= 103
• board and word consists only of lowercase and uppercase English letters.

문제 풀이

이 문제는 주어진 2차원 문자 배열에서 상하좌우로 이동하여 만들 수 있는 글자 중 word 라는 글자와 동일한 경우가 있는지를 확인하는 문제입니다.

예를 들어 위와 같은 배열과 ABCCED라는 word가 주어졌다면 2차원 배열의 임의의 지점에서 시작하여 word를 만들 수 있는지를 확인하는 문제입니다.

 

까다로운 점은 시작점이 2차원 배열의 모든 지점일 수 있다는 점과 한 번 방문한 곳은 또 방문할 수 없다는 점이었어요.

저는 방문한 것을 기록하기 위한 배열을 하나 만들어줬고 모든 글자의 경우를 보기 위해 dfs를 사용해줬습니다.

dfs를 수행하며 방문 여부와 기존에 만들던 문자열을 계속 수정해줘야 올바른 답을 찾을 수 있었습니다.

 

소스 코드

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        
        let dx: [Int] = [0,0,-1,1]
        let dy: [Int] = [-1,1,0,0]
        
        let m = board[0].count
        let n = board.count
        var visited: [[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)

        let goal = word.map({Character(extendedGraphemeClusterLiteral: $0)})
        var now: [Character] = []
        var stack: [[Int]] = []
        var result: Bool = false
        
        func dfs() {
            if stack.isEmpty {
                return
            }
            if result {
                return
            }
            let nowIndex = stack.popLast()!
            let nowChar = board[nowIndex[1]][nowIndex[0]]
            if !visited[nowIndex[1]][nowIndex[0]] {
                // 현재 값이 목표값과 같다면
                if nowChar == goal[now.count] {
                    now.append(nowChar)
                    visited[nowIndex[1]][nowIndex[0]] = true
                    if now == goal {
                        result = true
                        stack = []
                        return
                    }
                    for i in 0..<4{
                        let newX = nowIndex[0] + dx[i]
                        let newY = nowIndex[1] + dy[i]
                        
                        if newX < 0 || newY < 0 || newX > m-1 || newY > n-1 {
                            continue
                        } else {
                            // 만약 이번 재귀에서 방문한 적이 없다면 스택에 넣은뒤 dfs 수행.
                            if !visited[newY][newX] {
                                stack.append([newX,newY])
                                dfs()
                                if result {
                                    break
                                }
                                visited[newY][newX] = false
                            }
                        }
                    }
                    // 만약 위의 반복문에서 답을 찾지 못했다면 이번 재귀에서 넣은 값은 절대로 답이 될 수 없으니 빼준다.
                    let _ = now.popLast()!
                } else {
                    return
                }
            } else {
                return
            }
        }
        for i in 0..<n {
            for j in 0..<m {
                stack.append([j,i])
                dfs()
                visited[i][j] = false
                // 현재 값들은 정답이 절대 아니므로 비워준다.
                now = []
            }
        }
        return result
    }
}