끔찍한 좀비 바이러스가 디지털 도시 곳곳으로 번지고 있습니다. 우리는 디지털 CDC(질병통제예방센터)에서 근무하는 연구원으로, 도시 지도를 분석해 어떤 지역이 좀비 바이러스에 오염되었는지 판별하는 임무를 맡고 있습니다. 이 정보는 디지털 군대가 폭격 목표 지점을 결정하는 데 사용됩니다.
문제 개요
이번 사례의 좀비들은 새로운 변종이라서 수직·수평 방향(상하좌우)으로만 이동할 수 있으며, 자신과 같은 숫자만 감염시킬 수 있습니다.
입력으로는 숫자로 채워진 2차원 배열(행렬)이 주어집니다.
- 미스터리하게도 환자 제로(최초 감염자)는 항상 도시의 북서쪽, 즉 행렬의
[0][0]위치에서 발견됩니다. - 전염병은 이 지점에서 출발해 왼쪽, 오른쪽, 위, 아래 방향으로 퍼져나갑니다.
우리가 작성해야 할 함수는 오염된 지역은 1, 바이러스가 없는 지역은 0으로 표시한 지도(2차원 배열)를 반환해야 합니다.
다시 말해, [0][0]과 같은 값을 가진 모든 요소 중에서, 다른 값이 저장된 칸을 거치지 않고 상·하·좌·우로만 이동해 도달할 수 있는 칸들을 모두 찾으면 됩니다.
풀이 접근 방법
이 문제는 대표적인 플러드 필(Flood Fill) 유형으로, 그래프 탐색 기법으로 깔끔하게 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.
- 인접 정보 생성: 행렬 전체를 한 번 순회하면서
[0][0]과 값이 같은 칸마다, 상하좌우 이웃 중 같은 값을 가진 칸의 좌표 목록을 저장합니다. 이때 배열 범위를 벗어나는 좌표는 자동으로 걸러집니다. - 탐색 준비: 결과 배열을 모두 0으로 초기화합니다.
- 깊이 우선 탐색(DFS):
[0, 0]에서 탐색을 시작하고, 방문하는 칸마다 결과 값을 1로 변경합니다. 이미 처리한 칸은 인접 정보를 제거해 재방문하지 않으므로 무한 루프를 방지할 수 있습니다.
코드 예시
다음은 이 로직을 자바스크립트로 구현한 코드입니다.
const arr = [
[9, 1, 2, 3, 4, 1, 2, 9],
[9, 9, 9, 2, 1, 5, 9, 9],
[9, 2, 9, 3, 7, 9, 1, 9],
[6, 9, 9, 9, 0, 9, 2, 9],
[5, 4, 3, 9, 9, 9, 4, 9],
[9, 3, 9, 5, 8, 9, 9, 9],
[9, 9, 9, 9, 9, 9, 7, 9],
[9, 9, 1, 2, 3, 9, 8, 9]
];
const findZombies = arr => {
let i, j, result = [],
zombie = arr[0][0],
tree = {};
const chance = ([i, j]) => {
if (!tree[i] || !tree[i][j]) return;
result[i][j] = 1;
var temp = tree[i][j];
tree[i][j] = undefined;
temp.forEach(chance);
}
for (i = 0; i < arr.length; i++) {
result.push([]);
for (j = 0; j < arr[i].length; j++) {
result[i].push(0);
if (arr[i][j] !== zombie) continue;
if (!tree[i]) tree[i] = {};
tree[i][j] = [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]].filter(([x, y]) => arr[x] && arr[x][y] === zombie);
};
};
chance([0, 0]);
return result;
};
console.log(findZombies(arr));
콘솔에는 다음과 같은 결과가 출력됩니다.
[ [ 1, 0, 0, 0, 0, 0, 0, 1 ], [ 1, 1, 1, 0, 0, 0, 1, 1 ], [ 1, 0, 1, 0, 0, 1, 0, 1 ], [ 0, 1, 1, 1, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 1, 1, 0, 1 ], [ 1, 0, 1, 0, 0, 1, 1, 1 ], [ 1, 1, 1, 1, 1, 1, 0, 1 ], [ 1, 1, 0, 0, 0, 1, 0, 1 ] ]
동작 원리 살펴보기
코드의 핵심 요소를 하나씩 짚어 보겠습니다.
zombie:[0][0]의 값을 저장해 기준값으로 사용합니다. 이 예제에서는9입니다.tree: 값이 기준값과 같은 각 칸에 대해, 감염 가능한 이웃 칸들의 좌표를 담은 객체입니다.filter()덕분에 행렬 밖의 좌표나 값이 다른 이웃은 자동으로 제외됩니다.chance: 실제 감염 확산을 시뮬레이션하는 재귀 함수입니다. 방문한 칸은result에서 1로 표시되고,tree[i][j]를undefined로 만들어 다시 방문하지 않도록 처리합니다.
주목할 점은, 값이 9라고 하더라도 [0][0]에서 상하좌우로 연결되어 있지 않은 영역은 오염되지 않은 것으로 처리된다는 것입니다. 예를 들어 마지막 행의 1, 2, 3처럼 다른 숫자에 의해 격리된 칸들은 그대로 0으로 남습니다.
이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(N × M)(N은 행의 개수, M은 열의 개수)로, 행렬의 모든 칸을 최대 한 번씩만 방문하므로 효율적입니다. 이런 패턴은 이미지 영역 채우기, 미로 경로 탐색, 섬의 개수 세기 등 다양한 그리드 문제에 응용할 수 있습니다.