https://leetcode.com/problems/word-search/
문제 파악
주어진 리스트에서 이어진 블럭으로 해당 word가 생성될 수 있는지 묻는 문제. 된다면 true 아니라면 false!
접근 방법
주어진 리스트를 먼저 보드 형태?로 만들어서 이후에 이어진 블럭에서 갈 수 있는 길이 정해져 있기 때문에 해당 word로 갈 수 있는 길이 있는지 확인해보고 리턴해주기. 완전 탐색을 통해 구현하면 될 것 같다. 답을 찾는 도중 막히면 되돌아가서 다시 답을 찾는 백트래킹 방법을 통해 풀어보면 될 것 같다.
코드 구현
# 초기 코드
ans = []
def backtracking(curr):
if len(curr) == len(word):
ans.append(curr[:])
return
for i in word:
if i not in curr:
curr.append(i)
backtracking(curr)
curr.pop()
backtracking([])
return ans하지만 현재 코드는 다음과 같은 문제들이 있다. 이 코드는 word의 모든 순열을 생성하는데 비해 board 내에서의 경로 탐색을 위해 조정해야 한다.
- 현재 경로 추적: 현재 셀과
word에서의 현재 위치를 추적한다. - 경로 탐색: 네 방향(위, 아래, 왼쪽, 오른쪽)으로 이동하면서 탐색한다.
- 중복 방지: 이미 방문한 셀을 다시 방문하지 않도록 관리한다.
- 경계 체크: 보드의 경계를 벗어나는 경우를 처리한다.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
path = set() # 방문한 셀을 추적하기 위한 집합
def backtrack(r, c, index):
# 단어의 모든 문자를 찾았을 때
if index == len(word):
return True
# 경계 검사 및 현재 셀의 문자 검사
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index] or (r, c) in path):
return False
# 현재 셀을 경로에 추가
path.add((r, c))
# 네 방향 탐색
res = (backtrack(r + 1, c, index + 1) or
backtrack(r - 1, c, index + 1) or
backtrack(r, c + 1, index + 1) or
backtrack(r, c - 1, index + 1))
# 백트래킹: 현재 셀을 경로에서 제거
path.remove((r, c))
return res
for i in range(rows):
for j in range(cols):
if board[i][j] == word[0]: # 단어의 첫 문자와 같은 셀에서 탐색 시작
if backtrack(i, j, 0):
return True
return False배우게 된 점
기존 내가 짠 코드에서는 경계 조건 처리와 중복 방지에 대해서 잘 처리하지 못했는데 이를 문제에 따라서 처리해야하고 어떻게 처리해야 하는지에 대해 고민해보게 되었다.
