👀 문제
https://leetcode.com/problems/word-search/
👊 도전
1. 설계
- DFS를 이용한다.
- 시작 지점을 찾고, 거기서 DFS를 돌린다. 만족하면 종료, 아니라면 다른 시작점이 있는지 찾는다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
*
* @author HEESOO
*
*/
class Solution {
int m,n,w;
char[] array;
public boolean exist(char[][] board, String word) {
m=board.length; // 행
n=board[0].length; // 열
w=word.length(); // 문자열 길이
array=word.toCharArray(); // word를 문자 하나하나 쪼개기
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
// 시작점을 찾았고, 거기서 DFS한 결과가 참이면
if(array[0]==board[i][j] && dfs(i, j, 0, new boolean[m][n], board)) return true;
}
}
return false;
}
public boolean dfs(int x, int y, int idx, boolean[][] visit, char[][] board){
if(idx==w) return true; // word 찾기 완료
// 배열을 벗어나거나, 방문한 곳이거나, 찾는 문자가 아니라면
if(x<0 || x>=m || y<0 || y>=n || visit[x][y] || board[x][y]!=array[idx]) return false;
// idx번째 문자가 일치
visit[x][y]=true; // 사용
// 현재 위치에서 갈 수 있는 경우 다 체크
boolean up=dfs(x-1, y, idx+1, visit, board);
boolean down=dfs(x+1, y, idx+1, visit, board);
boolean left=dfs(x, y-1, idx+1, visit, board);
boolean right=dfs(x, y+1, idx+1, visit, board);
// 하나라도 true면 true
if(up || down || left || right) return true;
visit[x][y]=false; // (x,y)를 사용하지 않는 경우를 위함
return false;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 시작 지점을 찾는다
- board에서 시작 지점을 찾는다. 거기서부터 DFS를 시작한다.
- DFS를 이용한다
- 일단 특정 위치에서 다음으로 타고타고 넘어가는 문제는 보통 DFS이다. 거기다가 상하좌우로 움직이는 거면 많이 익숙쓰
- 파라미터 x, y는 현재 내 위치, idx는 word(String 체크를 편하게 하기 위해서 char 배열로 바꿨다)에서 체크할 곳, visit는 원소 방문여부 저장하는 배열이다.
- dfs()로 word를 체크한다. idx==w이면 문자열 체크가 무사히 끝났다는 것이므로 true를 리턴한다.
- 현재 위치 (x,y)까지는 word의 idx까지의 문자가 일치한다는 것이다. 따라서 지금 위치에서 상하좌우 중에 다음 문자와 일치하는 곳이 있는지 체크한다.
- 넷 중 하나라도 true이면 된다.
- 위에까지는 (x,y)를 사용한다는 가정 하에 진행한 것이다. (x,y)를 사용하지 않고 그냥 넘어갈 수도 있으므로, visit[x][y]=false로 처리하여 이 경우를 체크한다.