[1스4코2파] # 220. LeetCode 79. Word Search

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (220차)
[4코1파] 2023.01.13~ (212일차)
[1스4코1파] 2023.04.12~ (123일차)
[1스4코2파] 2023.05.03 ~ (101일차)

Today :

2023.08.12 [220일차]
backtracking
https://leetcode.com/problems/word-search/

LeetCode 79. Word Search

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

문제 설명

MxN의 문자열로 구성된 board가 주어질 때, 주어진 word에 해당하는 문자열이 있으면 true, 없으면 return 함
문자열을 search 할 때, 수직 혹은 수평방향으로 이웃한 문자열의 조합이 가능함!

문제 풀이 방법

MxN matrix 내의 한 좌표에서 수직 및 수평으로 움직일 수 있기 때문에 현재 좌표 내에서 위,아래,오른쪽,왼쪽으로 움직여가면서 찾을 수 있다.범위는 MxN 안에서만 돌아가고, 현재 좌표 기준으로 한번 방문했던 곳은 재방문하지 않게 break 걸어주는 조건이 필요함
dfs와 recursive로 푸는 문제

dfs로 풀고 base 조건은 현재 좌표가 주어진 matrix의 범위 안에서 도는 것과 recursive로 좌표와 함께 +1씩 증가하는 i 변수의 값을 주는데, 해당 word의 인덱스 i 값과 현재 좌표의 문자열이 같은지 확인하는 것.
한번 방문했던 좌표인지 확인하는 것임. 위의 조건들이 하나라도 해당된다면 False 이다.

해당 조건들을 다 피해간다면 True임 이를 brute force로 모든 matrix에서 한번씩 수행함

내 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        ROW, COL = len(board), len(board[0])
        visited = set()
        
        def dfs(r,c,i):
            if i == len(word):
                return True
            if (0>r or 0>c or ROW <=r or COL <= c) or (word[i] != board[r][c]) or ((r,c) in visited):
                return False

            visited.add((r,c)) 
            res = (dfs(r+1, c, i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1))
            visited.remove((r,c))
            return res
                    
        for r in range(ROW):
            for c in range(COL):
                if dfs(r, c, 0):
                    return True

        return False

증빙

여담

언뜻 기억나는 dfs .. 아직까지 완전한 조건을 못짜는게 함정임