https://leetcode.com/problems/word-search/description/
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.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Constraints:
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
또 코드로 게임짜기인데
싫어도 어쩌겠나 ㅠㅠ 시키니까 해야지
이런 건 문제 푸는 것도 어렵지만, 문제 이해하는 거 자체가 어렵다
1. Python
뇌 꼬인다. 분명 될 거 같은데 왜 결과가 안 나오지..
아래는 내가 짠 코드인데 틀린 코드라고 한다.
솔루션을 모르겄다...
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# m(x-axis) * n(y-axis) grid
m = len(board[0])
n = len(board)
direction = [[1,0],[-1,0],[0,1],[0,-1]]
# Recursive?
def search(a :int,b:int,cnt:int) -> bool:
if cnt == len(word) : return True
if board[a][b] == word[cnt]:
cnt+=1
for dx, dy in direction:
new_x = a+dx
new_y = b+dy
if 0<=new_x<n and 0<=new_y<m:
if search(new_x,new_y,cnt): # added cnt
return True
else:
return False
for i in range(n):
for j in range(m):
if search(i,j,0) :return True
return False
대체 어떻게 풀어나가면 될까..
아래는 솔루션 코드..
좀 현타가 온다 ㅠ
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# m(x-axis) * n(y-axis) grid
m = len(board[0])
n = len(board)
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)] # 상하좌우 이동 방향
# Backtracking search function
def search(a: int, b: int, cnt: int) -> bool:
# 단어를 모두 찾았으면 True 반환
if cnt == len(word):
return True
# 보드의 경계를 벗어나거나, 현재 문자가 일치하지 않으면 False 반환
if a < 0 or a >= n or b < 0 or b >= m or board[a][b] != word[cnt]:
return False
# 방문한 셀을 '#'로 표시해 중복 방문 방지
temp = board[a][b]
board[a][b] = '#'
# 상하좌우로 이동하여 다음 문자 탐색
for dx, dy in direction:
new_x, new_y = a + dx, b + dy
if search(new_x, new_y, cnt + 1): # 다음 문자를 찾으러 재귀 호출
return True
# 탐색을 마친 후 셀의 값을 원래대로 복구
board[a][b] = temp
return False
# 모든 셀을 시작점으로 탐색
for i in range(n):
for j in range(m):
if search(i, j, 0): # 단어의 첫 글자부터 시작
return True
return False
위 답안 코드를 필두로 내 코드를 수정해보았는데,
결론은 방문했던 Node를 체크해줘야 한다는 것이다. 왜냐하면 Direction은 상하좌우 모든 방향으로 이동하기 때문에, 내가 지금 Node에서 다음 Node로 이동했다가 다시 지금 Node로 돌아올 수가 있어서 문제가 있다. 그러면 cnt만 올라가서 어떻게 되든 True를 Return하게 되는 오류가 발생한다.
그래서 내 코드를 좀 수정해보았고, Node가 1개 뿐인 Edge case도 좀 추잡스럽게 관리하여 코드로 적었다.
하.. 백프로 내 힘으로 코드를 완성시키고 싶었는데 ㅠ 이런 디테일 살리기가 쉽지가 않네
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# m(x-axis) * n(y-axis) grid
m = len(board[0])
n = len(board)
direction = [[1,0],[-1,0],[0,1],[0,-1]]
# Recursive?
def search(a :int,b:int,cnt:int) -> bool:
if cnt == len(word) : return True
if board[a][b] == word[cnt]:
if len(word) == 1 : return True # edge case
temp = board[a][b]
board[a][b] = "^" # 방문 node 관리
cnt+=1
for dx, dy in direction:
new_x = a+dx
new_y = b+dy
if 0<=new_x<n and 0<=new_y<m:
if search(new_x,new_y,cnt): # added cnt
return True
board[a][b] = temp
else:
return False
for i in range(n):
for j in range(m):
if search(i,j,0) :return True
return False
좀 깔끔하게 정리해서 C++로도 코드를 짜보자.
2. C++
하나 알게된 건, class 내부에서 멤버변수로 선언한 container, variable들은 다른 method에서 접근이 가능하다는 것이다.
특정 method에서 해당 멤버 변수를 initialize 해주면 된다. 아래의 경우, exist 함수가 반드시 실행되어야 search가 실행되므로 이렇게 코드를 짤 수 있다는 것이다.
class Solution {
public:
vector<pair<int,int>> direction = {{1,0},{-1,0},{0,1},{0,-1}};
vector<vector<char>> vec;
string w;
bool search(int x, int y, int cnt){
if(cnt==w.size()) return true;
if(x<0 || x>=vec.size() || y<0 || y>=vec[0].size() || vec[x][y] != w[cnt]) return false;
char temp = vec[x][y];
vec[x][y] = '&';
for(auto direc : direction){
int dx = x + direc.first;
int dy = y + direc.second;
if(search(dx,dy,cnt+1)) return true;
}
vec[x][y] = temp;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
vec = board;
w = word;
int m = board[0].size();
int n = board.size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(search(i,j,0)) return true;
}
}
return false;
}
};
test 를 해보았다.
class Sol{
public:
int a = 3;
int b;
vector<int> vec = {6,87,9};
vector<int> vec2;
int test1(int c, int d){
cout << a << endl;
vec2 = {999,909};
return -1;
}
int test2(void){
for(auto x : vec){
cout << x << " ";
}
cout << endl;
for(auto x : vec2){
cout << x << " ";
}
return -1;
}
};
int main(){
Sol s;
s.test1(6,7);
s.test2();
}
3
6 87 9
999 909
이렇게 class 안 에서 선언된 멤버변수는 그 안에 다른 method들이 서로 엮여있지 않아도 자유롭게 수정/이용이 가능하다.
근데 여기서 main의 test1 / test2 순서를 바꿔보면 test2의 vec2는 출력되지 않는다.
왜냐하면 test1이 실행이 되어야 비로소 vec2가 test1 안의 내용으로 정의가 되기 때문이다.
class Sol{
public:
int a = 3;
int b;
vector<int> vec = {6,87,9};
vector<int> vec2;
int test1(int c, int d){
cout << a << endl;
vec2 = {999,909};
return -1;
}
int test2(void){
for(auto x : vec){
cout << x << " ";
}
cout << endl;
for(auto x : vec2){
cout << x << " ";
}
return -1;
}
};
int main(){
Sol s;
s.test2();
s.test1(6,7);
}
6 87 9
3
몰랐던 사실인데 ㅎㅎ;;
또 하나 배워갑니다~