[Grind75-LeetCode] Word Search - Medium
접근
- dfs
풀이
2차원 배열에 문자들이 저장되어 있고 문자들을 이어 주어진 단어를 만들 수 있는지 검사하는 문제이다. 상하좌우로 단어를 연결할 수 있기 때문에 dfs를 사용해 풀어주었다.
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean[][] isVisited = new boolean[board.length][board[0].length];
if (dfs(board, word, 0, isVisited, i, j)) {
return true;
}
}
}
}
return false;
}상하좌우 이동을 위한 배열을 만들고 2차원 배열을 순회하며 주어진 단어의 첫 번째 문자와 배열에 들어있는 문자가 같을 때 dfs를 시작한다.
private boolean dfs(char[][] board, String word, int index, boolean[][] isVisited, int i, int j) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}기본적으로 인덱스 값이 검사할 문자의 길이가 되면 배열을 통해 문자를 만들 수 있다는 뜻으로 true를 반환한다. 다음은 현재 상태에서 진행 여부를 검사하는 단계로 좌표가 배열 범위 밖이거나 이미 방문한 곳이거나 다음 문자에 해당하는 값이 아니라면 더 이상 진행하지 않는다.
isVisited[i][j] = true;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (dfs(board, word, index + 1, isVisited, nx, ny)) {
return true;
}
}
isVisited[i][j] = false;
return false;
}진행을 할 수 있는 상태라면 현재 좌표의 방문 체크를 수행하고 다음 단계로 진행하게 되고 다시 방문 상태를 false로 바꿔 여러 경로 탐색을 가능하게 해 준다.
dfs for 문 사용 x
생각보다 성능이 떨어져 일단 for문을 사용하지 않게 변경해 봤다. 좌표 값을 계산하고 하는 과정을 생략하고 4방향 직접 입력을 해주었다.
private boolean dfs(char[][] board, String word, int index, boolean[][] isVisited, int i, int j) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
isVisited[i][j] = true;
if (
dfs(board, word, index + 1, isVisited, i + 1, j) ||
dfs(board, word, index + 1, isVisited, i - 1, j) ||
dfs(board, word, index + 1, isVisited, i, j + 1) ||
dfs(board, word, index + 1, isVisited, i, j - 1)
) {
return true;
}
isVisited[i][j] = false;
return false;
}for문 대신 4방향 중 한 방향에서라도 문자열 완성이 가능하면 true를 반환받는 형식이다.
192ms에서 149ms로 생각보다 많이 단축되었다.
방문 배열 사용 x + 최적화
앞의 성능이 좋은 코드들은 어떤 방식으로 풀어졌나 봤다. dfs를 통해 풀어지는 건 거의 동일했으나 방문 배열을 추가로 사용하냐 안 하냐의 차이가 있었다. 방문 배열을 사용하는 대신 dfs를 진행하며 배열의 값을 직접 변경하여 방문 표시를 진행하는 방식이었다.
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
char[] wordArr = word.toCharArray();
if (!count(board, wordArr, m, n)) {
return false;
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (dfs(r, c, 0, board, wordArr)) {
return true;
}
}
}
return false;
}dfs를 수행하는 과정 이전 배열에 문자열을 구성하기 위한 문자의 개수가 충분한지 검사하는 과정이 존재했다.
public boolean count(char board[][], char[] wordArr, int m, int n) {
int[] charCounter = new int[123];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
charCounter[board[r][c]]++;
}
}
for (char c : wordArr) {
if (--charCounter[c] < 0) {
return false;
}
}
if (charCounter[wordArr[0]] > charCounter[wordArr[wordArr.length - 1]]) {
int i = 0, j = wordArr.length - 1;
while (i < j) {
char temp = wordArr[i];
wordArr[i++] = wordArr[j];
wordArr[j--] = temp;
}
}
return true;
}복잡해 보이지만 영어 대소문자의 아스키코드 값을 이용해 개수를 저장할 배열을 만들고 우선 문자열을 구성하기 위한 문자의 개수가 충분한지 검사한다. 개수가 충분하다면 최적화를 위한 연산이 존재하는데 단어의 앞 뒤를 검사하여 단어를 역순으로 뒤집는 과정이다. 이 과정을 왜 수행하는지 이해하려면 단어를 찾는 과정을 생각해봐야 한다. 문자열을 구성할 수 있는지 검사하기 위해선 보통 문자열의 앞부분부터 검사를 시작하게 된다. 만약 문자열이 "abcd"라면 배열에 값이 a인 곳에서 모두 검사가 일어나게 되고 수많은 a들 중 올바른 경로가 1개밖에 없다면 그 1번의 연산 외에는 모두 불필요한 연산이 일어났던 것이다. 그러나 만약 배열 내에 d가 1개만 존재한다면 d부터 역순 검사를 통해 1번의 연산으로 올바른 경로를 찾을 수 있는 것이다. 물론 맨 앞 문자나 맨 뒷 문자가 1개 이상씩 존재하겠지만 둘 중 더 작은 부분에서 검사를 시작해 불필요한 연산의 수를 줄이기 위한 최적화 과정이다.
private boolean dfs(int r, int c, int idx, char[][] board, char[] wordArr) {
if (idx == wordArr.length) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != wordArr[idx++]) {
return false;
}
board[r][c] = '#';
boolean found = dfs(r - 1, c, idx, board, wordArr) ||
dfs(r + 1, c, idx, board, wordArr) ||
dfs(r, c - 1, idx, board, wordArr) ||
dfs(r, c + 1, idx, board, wordArr);
board[r][c] = wordArr[idx - 1];
return found;
}dfs를 진행하는 부분은 크게 다를 게 없다. 방문 배열을 사용하는 대신 해당 자리를 알파벳 외의 문자로 변경해 방문했음을 표시하고 다음 단계로 진행한다. 그리고 다시 해당 지점에서 다른 경로 탐색을 위해 원래 있던 문자로 다시 변경해 준다.
방문 배열을 사용하지 않아 성능이 개선된 것보다 최적화 과정에서 성능 개선이 많이 일어난 코드인 것 같다.
최적화 코드를 주석처리 했을 땐 112ms로 방문 배열을 사용하던 코드 보단 빨라졌지만 최적화 코드의 차이가 어마어마하다.
전체 코드
dfs
class Solution {
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean[][] isVisited = new boolean[board.length][board[0].length];
if (dfs(board, word, 0, isVisited, i, j)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, boolean[][] isVisited, int i, int j) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
isVisited[i][j] = true;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (dfs(board, word, index + 1, isVisited, nx, ny)) {
return true;
}
}
isVisited[i][j] = false;
return false;
}
}
dfs for문 사용 x
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean[][] isVisited = new boolean[board.length][board[0].length];
if (dfs(board, word, 0, isVisited, i, j)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, boolean[][] isVisited, int i, int j) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
isVisited[i][j] = true;
if (
dfs(board, word, index + 1, isVisited, i + 1, j) ||
dfs(board, word, index + 1, isVisited, i - 1, j) ||
dfs(board, word, index + 1, isVisited, i, j + 1) ||
dfs(board, word, index + 1, isVisited, i, j - 1)
) {
return true;
}
isVisited[i][j] = false;
return false;
}
}
방문 배열 x + 최적화
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
char[] wordArr = word.toCharArray();
if (!count(board, wordArr, m, n)) {
return false;
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (dfs(r, c, 0, board, wordArr)) {
return true;
}
}
}
return false;
}
private boolean dfs(int r, int c, int idx, char[][] board, char[] wordArr) {
if (idx == wordArr.length) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != wordArr[idx++]) {
return false;
}
board[r][c] = '#';
boolean found = dfs(r - 1, c, idx, board, wordArr) ||
dfs(r + 1, c, idx, board, wordArr) ||
dfs(r, c - 1, idx, board, wordArr) ||
dfs(r, c + 1, idx, board, wordArr);
board[r][c] = wordArr[idx - 1];
return found;
}
public boolean count(char board[][], char[] wordArr, int m, int n) {
int[] charCounter = new int[123];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
charCounter[board[r][c]]++;
}
}
for (char c : wordArr) {
if (--charCounter[c] < 0) {
return false;
}
}
if (charCounter[wordArr[0]] > charCounter[wordArr[wordArr.length - 1]]) {
int i = 0, j = wordArr.length - 1;
while (i < j) {
char temp = wordArr[i];
wordArr[i++] = wordArr[j];
wordArr[j--] = temp;
}
}
return true;
}
}'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Minimum Height Trees JAVA (0) | 2024.11.23 |
|---|---|
| [Grind75-LeetCode] Find All Anagrams in a String JAVA (0) | 2024.11.22 |
| [Grind75-LeetCode] Letter Combinations of a Phone Number JAVA (1) | 2024.11.20 |
| [Grind75-LeetCode] Container With Most Water JAVA (0) | 2024.11.19 |
| [Grind75-LeetCode] Construct Binary Tree from Preorder and Inorder Traversal JAVA (1) | 2024.11.18 |