문제 링크: https://leetcode.com/problems/word-search/description/
파이썬 소스: https://bit.ly/4cSOHmK
백트랙킹(backtracking)과 BFS 방식으로 풀 수 있는 문제입니다. 이번에는 백트랙킹으로 문제를 풀어 보겠습니다.
word변수의 첫번째 글자를 board에서 찾아야 나머지 글자들을 맞출 수 있습니다. 첫번째 글자를 찾는 코드를 작성해 보겠습니다.
|
MAX_ROW, MAX_COL = len(board), len(board[0]) |
2차원 배열인 board의 모든 칸을 방문하기 위해서, 가로, 세로 길이를 두 변수에 저장합니다.
for y in range(MAX_ROW): |
두개의 for루프를 사용해서, board의 모든 칸을 방문합니다. 변수 word의 첫번째 글자 word[0]이 board[y][x]와 같으면 재귀함수 rec()를 호출하게 됩니다.
이 때, visited[y][x]에 True를 저장하여, 중복해서 방문하는 것을 방지합니다.
Example 3번을 보면, “ABCE’가 주어질 때, False가 결과인 것을 볼 수 있습니다.
board[0, 0]이 word[0] A와 같으므로 방문함
board[0, 1]이 word[1] B와 같으므로 방문함
board[0, 2]이 word[2] C와 같으므로 방문함
여기서 중복 방문이 허용된다면, board[0, 1] B를 방문할 수도 있습니다. 하지만, 문제에서는 중복된 방문을 허용하지 않습니다. 문제에서도 아래와 같이, ‘같은 글자가 한번이상 사용되면 안된다.’라고 표기하고 있습니다.
The same letter cell may not be used more than once.
재귀함수가 리턴되면, 해당 칸은 아래의 경우에 다시 사용될 수 있으므로, visited[y][x] = False로 저장합니다.
board
A A B
C X X
X X X
word: AAC
위와 같이 board와 word가 주어지면, board[0][0]이 word[0] A와 같기 때문에, 재귀함수가 호출되지만, board[0][1]로 이동 후에, [0, 1]에서 이동할 수 있는 위/아래/좌/우 칸에 C 가 없기 때문에 [0, 0]에서 시작해서, AAC를 찾는 것은 실패합니다.
하지만, board[0,1]에서 A를 만나서 AAC를 찾기 시작하면 아래 같은 순서로 AAC를 찾을 수 있습니다.
[0, 1] A -> [0, 0] A -> [1, 0] B
따라서, [0, 0]을 방문한 뒤에, visited[0, 0]을 False로 저장해 두어서, 위와 같이 두번째에 [0, 0]을 방문할 수 있도록 해야 합니다.
이제 재귀 호출할 rec()함수를 코딩해 보겠습니다.
우선 재귀함수임으로 재귀 호출이 멈출 stop condition을 알아보겠습니다.
def rec(board, y, x, word, depth, depth_max): |
변수 depth는 한글자씩 찾을 때 마다, 1씩 증가합니다. depth_max는 len(word)값과 같습니다. 따라서, 두 변수가 같다는 것은, word의 모든 글자를 board에서 찾았다는 의미임으로, True를 리턴하고, 재귀함수 호출을 더 이상 하지 않습니다.
for dy, dx in [[-1, 0], [0, 1], [1, 0], [0, -1]]: |
인자 y, x 는 word의 글자가 마지막으로 board와 같은 위치 입니다. 따라서, y, x에서 위/아래/좌/우 4가지 방향으로 다음 글자가 같은지 확인해 봐야 합니다.
For 루프에서 4가지 방향으로 이동하는 dy, dx값을 가지고 와서, 새로 이동할 위치인 ny, nx 값을 알 수 있습니다. ny, nx위치는 board의 밖에 있을 수도 있기 때문에, board안에 있는지 아래와 같이 확인을 합니다. Board의 안에 위치한 값만 사용합니다.
if 0 <= ny < MAX_ROW and 0 <= nx < MAX_COL: |
변수 word에 있는 다음 글자와 board[ny][nx]의 글자가 같은지 확인하고, 기존에 방문한 위치가 아닌지도 확인합니다.
if board[ny][nx] == word[depth] and False == visited[ny][nx]: |
이제 재귀함수를 호출할 차례 입니다.
재귀 함수를 호출 하기 전에, ny, nx를 방문했으므로, visited[ny][nx]에 True로 저장을 하고, 재귀함후를 호출 합니다.
if rec(board, ny, nx, word, depth + 1, depth_max): |
재귀함후가 리턴되면, ny, nx는 앞에서 설명한 것과 같이, 다시 방문할 수 있기 때문에, visited[ny][nx]에 False를 저장합니다.
변수 word의 모든 글자를 board에서 모두 찾게 되면, 재귀함수 rec()의 stop condition에서 True가 리턴되구요, 재귀함수 rec()가 리턴 True임으로, 재귀적으로 호출된 rec()는 모두 True를 리턴하게 됩니다.
위와 같이 구현한 전체 코드는 아래와 같습니다.
from typing import List
|
궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.
코데풀 유튜브 구독 부탁드립니다.
댓글 없음:
댓글 쓰기