문제
입력으로 board와 word가 주어집니다. 해당 board에 word가 존재하면 True를 반환하고 그렇지 않다면 False를 반환합니다. word는 각 인접 cell들이 상하좌우로 붙은 형태로 만들어질수있습니다.
위 그림에서는 board가 주어지고 ABCCDE라는 word가 주어졌을때 해당 word를 board에서 찾은 모습입니다. 결과는 True가 되어야할것입니다.
풀이
제가 만든 함수는 is_word_valid(self, board, y, x, word)라는 함수로써 board[y][x]의 값과 word의 첫번째 값이 동일한지 판단하는 함수입니다. 이 함수를 이용, 재귀를 사용해서 문제를 풀려고 합니다.
이 함수는 언제 끝나야할까요? word가 비었을때, 혹은 y,x가 유효한 범위에 있지 않았을때입니다. word값이 존재하는 상황이라면 word의 첫번째 값과 현재 board[y][x]값을 비교하고 동일하지 않다면 False를 리턴합니다. 동일할 경우. word의 다음값에 대해 판단이 이루어져야합니다. 여기서 현재의 값은 다시 사용되면 안되므로 '#'으로 바꿔줍니다. 이후,
is_word_valid(self, board, y, x, word[1:])라는 함수를 호출해야합니다. 물론 여기서 y,x는 현재 인덱스의 상하좌우가 들어가야 합니다.
재귀 종료의 순서가 중요합니다. 초기 예외처리 상황에서 word가 비었을때를 처리하는 명령보다 y,x가 유효한지를 처리하는 명령을 먼저 수행한다면 다음과 같은 상황에서 틀린 결과를 가지게 됩니다.
현재 y,x가 유효한지 판단합니다. -> 유효합니다.
word가 비었는지 판단합니다. -> 아직 비어있지 않습니다.
'A'와 word[0], 즉 현재 y,x가 가리키는 board의 값과 word의 앞글자를 비교합니다. -> 같습니다. 현재 값을 확인했으므로 현재값을 #로 만듭니다.이제 상하좌우를 둘러봐야합니다.
상하좌우로 이동한 경우를 별표로 표시한것입니다. 이 경우에는 word가 비어진 상태. 즉 정답인 상태임에도 불구하고 별표 좌표는 유효한 좌표가 아니므로 4개의 경우 모두 False를 반환합니다. 최종정답이 True임에도 불구하고 False를 반환하는 경우가 생깁니다. 따라서 word가 비었는지 판단하는 과정이 선행되어야 합니다.
코드
'''
Created by jun on 21/05/02
'''
class Solution:
def is_range_valid(self, y, x, ny, nx):
return 0 <= y < ny and 0 <= x < nx
def is_word_valid(self, board, y, x, word):
if not word:
return True
if not self.is_range_valid(y,x,len(board),len(board[0])):
return False
if word[0] != board[y][x]:
return False
tmp = board[y][x]
board[y][x] = '#'
for dy , dx in ((-1,0),(+1,0),(0,-1),(0,+1)):
if self.is_word_valid(board,y+dy,x+dx,word[1:]):
return True
board[y][x] = tmp
return False
def exist(self, board: List[List[str]], word: str) -> bool:
for y in range(len(board)):
for x in range(len(board[0])):
if self.is_word_valid(board,y,x,word):
return True
return False새로 알게된 사실
재귀 함수 종료조건 순서의 중요성
