SeangG
def _(): _()
SeangG
전체 방문자
오늘
어제
  • 분류 전체보기 (37)
    • Programming Language (0)
      • Python (0)
      • Web (0)
    • Algorithm (34)
    • Art (0)
      • 3D Modeling (0)
      • Pixel (0)
      • Picture (0)
    • Game (0)
    • Project (3)
      • Problems (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Tree
  • Fast Refresh
  • next.js
  • 문자열
  • dfs
  • github oauth
  • Daily Question
  • Python
  • LeedCode
  • BFS
  • 매핑 테이블
  • graph
  • spring boot
  • react.js
  • WSL
  • Queue
  • Leecode
  • 로마 숫자
  • leetcode
  • string

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
SeangG
Algorithm

[LeetCode] 79. Word Search (Daily Question)

[LeetCode] 79. Word Search (Daily Question)
Algorithm

[LeetCode] 79. Word Search (Daily Question)

2024. 4. 3. 14:24

문제


Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

 

영문자로 구성된 보드와 단어가 주어졌을 때, 단어가 보드에 있는지 판별하는 문제이다.

문자끼리는 가로 및 세로로 연결되어 있어야 한다.  

 

에를 들면,

board는 [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], 

word는 "ABCCED" 가 주어졌을 때

왼쪽 그림과 같은 형태로 단어가 존재하므로 True를 반환한다.

 


 

풀이

아이디어

DFS를 사용한다.

보드의 최대 크기는 6*6으로 한 칸 한 칸 탐색하며 문자가 만들어지는지 판별해도 괜찮을 듯 하다.

 

코드

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

        # 탐색하는 함수
        # pos: 현재 칸 위치, searched: 단어를 만들기 위해 탐색한 경로
        def search(pos, searched):
            
            # 현재 탐색중인 word의 문자 차례
            ln = len(searched)+1

            # 주어진 문자열이 완성된 경우
            if ln == len(word): return True

            x, y = pos
            searched.append(pos)
            
            # 주변 칸에 다음 문자가 있는지 확인 후 재귀
            if (x-1, y) not in searched and x-1 >= 0 and board[x-1][y] == word[ln]:
                # 리스트를 복사하려면 .copy()를 해줘야 함
                # 안하면 함수 내에서 값을 바꿨을 때 외부에 영향을 미침
                if search((x-1, y), searched.copy()): return True

            if (x+1, y) not in searched and x+1 < len(board) and board[x+1][y] == word[ln]:
                if search((x+1, y), searched.copy()): return True

            if (x, y-1) not in searched and y-1 >= 0 and board[x][y-1] == word[ln]:
                if search((x, y-1), searched.copy()): return True

            if (x, y+1) not in searched and y+1 < len(board[0]) and board[x][y+1] == word[ln]:
                if search((x, y+1), searched.copy()): return True

            return False

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and search((i, j), []): 
                    return True

        return False

 

후기


난이도

탐색알고리즘에 익숙해져 있기 때문에 어렵지는 않았다.

단어를 만들기 위해 탐색했던 경로는 다음 경로에서 제외해주어야 한다는 예외사항이 있었지만,그 외에는 따로 없어서 까다롭지는 않았다.

 

주의해야할 사항으로는 함수의 인자값으로 리스트를 넣을 때, .copy()를 통해 복사된 상태로 넣어주어야 한다는 것이다.

그냥 전달하면 함수 내부에서 리스트의 요소를 변경했을 때 외부까지 반영이 된다.

 

다른 풀이

BFS를 사용해 단어가 될 수 있는 후보들만 남기고 계속 탈락시키는 방식도 가능할 듯 싶다.

'Algorithm' 카테고리의 다른 글

[LeetCode] 1544. Make The String Great (Daily Question)  (0) 2024.04.05
[LeetCode] 1111. Maximum Nesting Depth of Two Valid Parentheses Strings  (0) 2024.04.04
[LeetCode] 1614. Maximum Nesting Depth of the Parentheses (Daily Question)  (0) 2024.04.04
[LeetCode] 12. Integer to Roman  (0) 2024.04.02
[LeetCode] 205. Isomorphic Strings (Daily Question)  (1) 2024.04.02
  • 문제
  •  
  • 풀이
  •  
  • 후기
'Algorithm' 카테고리의 다른 글
  • [LeetCode] 1111. Maximum Nesting Depth of Two Valid Parentheses Strings
  • [LeetCode] 1614. Maximum Nesting Depth of the Parentheses (Daily Question)
  • [LeetCode] 12. Integer to Roman
  • [LeetCode] 205. Isomorphic Strings (Daily Question)
SeangG
SeangG

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.