코딩 테스트는 많은 개발자들이 치르며, 다양한 알고리즘 문제를 통해 자신의 능력을 평가받습니다. 이번 글에서는 ‘경로 찾기’ 문제를 통한 알고리즘 문제 해결 과정을 자세히 살펴보겠습니다. 이 문제는 DFS(Depth-First Search) 또는 BFS(Breadth-First Search)와 같은 그래프 탐색 기법을 사용하는 데에 적합합니다.
문제 설명
주어진 2D 격자에서 시작점에서 도착점으로 가는 경로를 찾아야 합니다. 격자의 각 셀은 이동할 수 있는지 없는지를 나타내며, 아래는 문제 조건입니다:
- 격자는 N x M 크기를 가진다.
- 각 셀은 0 또는 1로 표시되며, 0은 이동할 수 있는 경로, 1은 막힌 경로를 뜻한다.
- 시작점은 (0, 0)이고, 도착점은 (N-1, M-1)이다.
- 상하좌우로 이동할 수 있다.
예시 입력
4 4
0 0 1 0
0 1 0 0
0 1 1 0
0 0 0 0
예시 출력
Yes
문제 해결 과정
이 문제를 해결하기 위해 우리가 사용할 알고리즘은 BFS입니다. BFS는 각 노드를 차례대로 탐색할 수 있어 최단 경로를 찾기에 유리합니다. 이를 수행하기 위해 아래와 같은 단계로 문제를 해결합니다:
1. 격자 공간 생성
입력받은 격자 정보를 배열로 변환합니다. 이를 통해 각 셀에 대한 접근과 이동을 용이하게 합니다.
2. BFS 초기화
시작점 (0, 0)을 큐에 추가합니다. 추가적으로 방문한 노드를 추적하기 위해 추가 배열을 사용합니다.
3. BFS 탐색 수행
큐가 비어있지 않은 동안 다음을 반복합니다:
- 큐에서 노드를 꺼내 현재 위치를 확인합니다.
- 현재 위치가 도착점 (N-1, M-1)인지 확인합니다. 맞으면 ‘Yes’를 출력하고 탐색을 종료합니다.
- 상하좌우로 이동할 수 있는 모든 셀에 대해 다음을 수행합니다:
- 셀의 경계 조건 및 방문 여부를 확인합니다.
- 셀의 값이 0이고, 미방문 상태라면 큐에 추가하고 방문 상태로 변경합니다.
모든 탐색이 끝난 후에도 도착점에 도달하지 못했다면 ‘No’를 출력합니다.
4. 코드 구현
function canReachDestination(grid) {
const N = grid.length;
const M = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const queue = [[0, 0]];
const visited = Array.from({length: N}, () => Array(M).fill(false));
visited[0][0] = true;
while (queue.length > 0) {
const [x, y] = queue.shift();
// 도착점 확인
if (x === N - 1 && y === M - 1) {
return "Yes";
}
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
// 경계조건과 방문여부 확인
if (nx >= 0 && ny >= 0 && nx < N && ny < M &&
!visited[nx][ny] && grid[nx][ny] === 0) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
return "No";
}
const grid = [
[0, 0, 1, 0],
[0, 1, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]
];
console.log(canReachDestination(grid)); // 결과: "Yes"
결론
이번 문제를 통해 BFS 알고리즘을 활용한 경로 찾기 문제를 해결해 보았습니다. 실제 코딩 테스트에서는 이러한 문제를 자주 만나게 되므로, 여러 알고리즘을 연습하여 다양한 문제에 대한 해결 능력을 기르는 것이 중요합니다. 다음 강좌에서는 다른 유형의 알고리즘 문제를 다뤄보도록 하겠습니다. 감사합니다!