03/11 코딩테스트 문제풀이 - 79. Word Search (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 79. Word Search (Medium)
• 문제 내용 : [링크]
  
  
  

내가 작성한 코드

class Solution:
    def exist(self, board, word):
        m = len(board)
        n = len(board[0])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        visit = [[False for _ in range(n)] for _ in range(m)]

        def is_in(x, y):
            if x>=0 and y>=0 and x<m and y<n:
                return True
            return False
        
        def backtrack(x, y, i, visit):
            if board[x][y] == word[i] and not visit[x][y]:
                if i == len(word)-1:
                    return True

                visit[x][y] = True

                for nx, ny in zip(dx, dy):
                    if is_in(x+nx, y+ny):
                        if backtrack(x+nx, y+ny, i+1, visit):
                            return True
                visit[x][y] = False

            return False
    
        for x in range(m):
            for y in range(n):
                if backtrack(x, y, 0, visit):
                    return True
        
        return False

• board 와 word가 주어졌을 때, board에서 인접한 글자를 연결했을 때 word를 출력할 수 있으면 True, 아니면 False를 반환하는 프로그램을 작성한다.

• 먼저 m,n을 board 의 행/열 개수로 설정한다.

• dx, dy를 통해 12시/3시/6시/9시 방향의 이동을 할 수 있는 리스트를 구현한다.

• visit array를 만들어 해당 좌표 방문 여부를 확인할 수 있도록 한다. (인접한 글자를 선택할 때, 한 번 선택한 좌표는 중복해서 선택할 수 없음)

• is_in(x,y) 를 통해, 해당 좌표가 board 안에 있는 지 확인하는 기능을 가지는 함수를 구현해준다. x, y가 각각 [0, m-1], [0, n-1] 범위 안에서 존재할 수 있다.

• 다음으로 완전탐색을 위해 backtrack(x, y, i, visit) 함수를 구현해준다. board의 좌표 중 하나를 시작점으로 가질 때, 해당 좌표에서 인접한 글자를 통해 word의 단어를 만들 수 있는 지 완전탐색 하면서 확인해야 한다.

• 해당 좌표의 board[x][y] 값이 word[i] 값과 같고, 그 좌표가 방문하지 않은 좌표일 때,(즉, visit[x][y] = False) 그 때 i값 (인덱스 값)이 len(word)-1인 경우, 이미 word를 완성한 경우이므로 True 값을 return 해 준다.

• 위의 경우가 아니라면, word를 만들기 위한 작업을 계속해야 한다. 우선 해당 좌표를 방문했으므로 visit[x][y]=True를 해 준다.

• 해당 좌표의 위/오른쪽/아래/왼쪽 좌표를 for문을 통해 탐색하면서, 해당 좌표가 board안에 위치하는지 확인한다. (if is_in(x+nx, y+ny):)

• 해당 좌표의 위/오른쪽/아래/왼쪽 좌표가 board안에 위치할 경우, 해당 좌표의 위/오른쪽/아래/왼쪽 좌표에서 다시 backtrack()을 실행해준다. 탐색한 값이 True가 나오면 최종으로 True값을 return 해 준다.

• True이 나오지 않은 경우, 다른 좌표에서 시도를 해봐야 하므로 방문했던 좌표들의 방문 여부를 다시 False로 바꿔준다.

• 위에서 구현한 backtrack 함수를 for문을 통해 board의 모든 좌표를 완전탐색하며 실행해준다.

• 백트래킹 중, backtrack(x, y, 0, visit) 값이 True가 나온다면, board 안에서 인접한 글자를 연결해 word를 만들 수 있으므로 True를 반환한다.

• 해당되는 경우가 없다면 False를 반환한다.

⭐⭐⭐⭐⭐

• array에서 백트래킹 구현하는 문제이다. 완전탐색 시, 조건을 주어 조건을 충족하는 경우에만 완전탐색 하도록 코드를 구현할 수 있다.