이번 글에서는 첫 번째 인수로 문자들이 담긴 2차원 배열(행렬)을, 두 번째 인수로 하나의 문자열을 받는 JavaScript 함수를 작성하는 방법을 살펴봅니다.
함수는 행렬에 포함된 문자들 중에서 같은 칸을 두 번 이상 사용하지 않고 상하좌우로 인접한 칸을 순서대로 연결했을 때, 두 번째 인수로 전달된 문자열과 정확히 일치하는 경로가 존재하는지 판별해야 합니다.
그러한 조합이 하나라도 존재하면 true를, 존재하지 않으면 false를 반환합니다.
문제 예시
입력 행렬과 찾고자 하는 문자열이 다음과 같다고 가정해 보겠습니다.
const arr = [
['s', 'd', 'k', 'e'],
['j', 'm', 'o', 'w'],
['y', 'n', 'l']
];
const str = 'don';이때 기대하는 출력은 다음과 같습니다.
const output = false;
'd'는 첫 번째 행의 두 번째 열에 있지만, 인접한 칸(왼쪽 's', 오른쪽 'k', 아래 'm') 어디에도 'o'가 없습니다. 따라서 'don'이라는 단어를 인접 칸을 연결해 만드는 것은 불가능하며 결과는 false가 됩니다.
구현 코드
다음은 깊이 우선 탐색(DFS)과 백트래킹을 활용한 전체 구현 코드입니다.
const arr = [
['s', 'd', 'k', 'e'],
['j', 'm', 'o', 'w'],
['y', 'n', 'l']
];
const str = 'don';
const containsWord = (arr = [], str = '') => {
if (arr.length === 0){
return false;
};
const height = arr.length;
const width = arr[0].length;
const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
const tryWord = (x, y, k) => {
if (arr[x][y] !== str[k]) return false;
if (k === str.length - 1) return true;
arr[x][y] = '*';
for (const [dx, dy] of dirs) {
const i = x + dx;
const j = y + dy;
if (i >= 0 && i < height && j >= 0 && j < width) {
if (tryWord(i, j, k + 1)) return true;
}
}
arr[x][y] = str[k]; // reset
return false;
};
for (let i = 0; i < height; i++) {
for (let j = 0; j < width; j++) {
if (tryWord(i, j, 0)) return true;
}
}
return false;
};
console.log(containsWord(arr, str));코드 동작 원리
- 시작점 탐색: 행렬의 모든 칸을 순회하며 각 칸을 단어의 시작 위치로 삼아 탐색을 시도합니다.
- DFS 재귀 호출: 현재 칸의 문자가 찾는 문자와 일치하면, 해당 칸을 임시로 '*'로 덮어써 한 경로 안에서 같은 칸이 재사용되지 않도록 합니다.
- 4방향 이동: 상, 하, 좌, 우 네 방향의 인접 칸을 확인하며 다음 문자를 찾고, 행렬 범위를 벗어나는 좌표는 무시합니다.
- 백트래킹: 현재 경로로 단어를 완성하지 못하면 덮어썼던 칸을 원래 문자로 되돌려 다른 경로 탐색에 영향을 주지 않도록 합니다.
- 종료 조건: 마지막 문자까지 모두 일치하면 즉시 true를 반환하고, 모든 시작점에서 실패하면 최종적으로 false를 반환합니다.
이 풀이의 시간 복잡도는 O(M × N × 3L)입니다. 여기서 M×N은 행렬의 크기, L은 문자열의 길이를 의미하며, 각 칸에서 되돌아가는 방향을 제외한 최대 세 방향으로 탐색이 분기되기 때문입니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
false