[LeetCode] 79. Word Search - 자바스크립트 0613

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

Word Search - LeetCode

 

출처 leetcode

이 문제는, dfs bfs 두문제 풀이가 가능하다. 하지만 여기서는 dfs로 문제를 풀이를 하기로 한다!

1. 이 문제는 중복으로 재방문을 하면 안되므로 visited라는 정렬을 만들어서 재방문을 체크하는 것이 중요하다. 문제가 살짝 길어질꺼같으니, function으로 분리하자. 여기서 h,와 w는 board의 length로 정해지게 만든다.

const falseDefault = function (h, w) {
    const visited = []
    for (let i = 0; i < h; i++) {
        let list = []
        for (let j = 0; j < w; j++) {
            list.push(false)
        }
        visited.push(list)
    }
    return visited
}

2. 1번에 있던 function에 h, w를 구하고 visited 값을 만든다.

    const h = board.length;
    const w = board[0].length;
    const visited = falseDefault(h, w)

3. dfs는 board와 visited를 사용하기 때문에 solution 함수안에 넣을 것이다. dfs함수를 작성한다. dfs의 변수는 baord의 위치와 word의 글자 index를 넣는다.

    const dfs = function (x, y, i) {
    }

4.[1] board x y가 word i 가 같을 때

    [2]x와 y가 board의 범위일 때

    [3]visited의 다음 칸이 false일 때

   dfs를 실행한다. 이때 처음 방문할 때는 방문은 true로 만든다.

        if (word[i] === board[y][x]) {
            visited[y][x] = true
            if (x > 0 && visited[y][x - 1] === false) {
                dfs(x - 1, y, i + 1)
            }
            if (y > 0 && visited[y - 1][x] === false) {
                dfs(x, y - 1, i + 1)
            }
            if (x < w - 1 && visited[y][x + 1] === false) {
                dfs(x + 1, y, i + 1)
            }
            if (y < h - 1 && visited[y + 1][x] === false) {
                dfs(x, y + 1, i + 1)
            }
        }

5. 이때 중요한 것은 방문을 하고 나오면 다시 비방문으로 수정해야한다.

        if (word[i] === board[y][x]) {
            visited[y][x] = true
            if (x > 0 && visited[y][x - 1] === false) {
                dfs(x - 1, y, i + 1)
                visited[y][x - 1] = false
            }
            if (y > 0 && visited[y - 1][x] === false) {
                dfs(x, y - 1, i + 1)
                visited[y - 1][x] = false
            }
            if (x < w - 1 && visited[y][x + 1] === false) {
                dfs(x + 1, y, i + 1)
                visited[y][x + 1] = false
            }
            if (y < h - 1 && visited[y + 1][x] === false) {
                dfs(x, y + 1, i + 1)
                visited[y + 1][x] = false
            }
        }

6. i가 word.length-1이 되었을 때, word[i]와 board[y][x]가 같아지는 경우에는 answer를 true로 하고, 아닌 경우 빈 값을 내보내게 한다. answer값은 밖에서도 확인이 되야하니 dfs 밖에 answer을 선언한다

        if (i === word.length - 1 && word[i] === board[y][x]) {
            answer = true
            return
        } else if (i === word.length - 1) {
            return
        }

    const h = board.length;
    const w = board[0].length;
    const visited = falseDefault(h, w)
    let answer = false
    const dfs = function (x, y, i) {
    //생략
    }

7. 모든 board에서 시행을 하고, 시행한 뒤에는 비방문 처리를 한다.

    for (let i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {

            dfs(j, i, 0)
            visited[i][j] = false
        }
    }

8. return answer

최종 풀이

var exist = function (board, word) {
    const h = board.length;
    const w = board[0].length;
    const visited = falseDefault(h, w)
    let answer = false
    const dfs = function (x, y, i) {

        if (i === word.length - 1 && word[i] === board[y][x]) {
            answer = true
            return
        } else if (i === word.length - 1) {
            return
        }
        if (word[i] === board[y][x]) {
            visited[y][x] = true
            if (x > 0 && visited[y][x - 1] === false) {
                dfs(x - 1, y, i + 1)
                visited[y][x - 1] = false
            }
            if (y > 0 && visited[y - 1][x] === false) {
                dfs(x, y - 1, i + 1)
                visited[y - 1][x] = false
            }
            if (x < w - 1 && visited[y][x + 1] === false) {
                dfs(x + 1, y, i + 1)
                visited[y][x + 1] = false
            }
            if (y < h - 1 && visited[y + 1][x] === false) {
                dfs(x, y + 1, i + 1)
                visited[y + 1][x] = false
            }
        }

    }
    for (let i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {

            dfs(j, i, 0)
            visited[i][j] = false
        }
    }
    return answer
};
const falseDefault = function (h, w) {
    const visited = []
    for (let i = 0; i < h; i++) {
        let list = []
        for (let j = 0; j < w; j++) {
            list.push(false)
        }
        visited.push(list)
    }
    return visited
}