[프로그래머스] JavaScript Lv2 - 무인도 여행(154540)

개요

문제 이름: 무인도 여행 (154540)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154540
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 5시간

 

문제 전문

설명

제한사항

입출력

 

 

문제 풀이

해설

이 문제는 2차원 격자 형태의 지도에서 연결된 무인도를 탐색하고, 각 무인도에서 최대로 머물 수 있는 일수를 계산하는 문제입니다. 문제를 해결하기 위해서는 그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색(DFS)을 활용합니다.

 

DFS는 그래프의 한 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식으로 진행됩니다. 즉, 한 방향으로 갈 수 있을 때까지 깊이 탐색하다가 더 이상 갈 수 없게 되면 이전 노드로 돌아와서 다른 방향으로 탐색을 계속하는 과정을 반복합니다. DFS는 스택(Stack) 자료구조를 활용하여 구현할 수 있으며, 이 문제에서는 재귀 함수를 사용하여 DFS를 구현했습니다.

 

문제 해결을 위한 접근 방식은 다음과 같습니다.

1. 주어진 지도의 각 위치를 탐색하면서, 아직 방문하지 않은 땅(숫자)을 발견하면 해당 위치에서 DFS를 시작합니다.
2. DFS 함수 내에서는 현재 위치가 유효한지 확인합니다. 지도 범위를 벗어나거나, 이미 방문한 위치이거나, 바다('X')인 경우 탐색을 종료합니다.
3. 현재 위치를 방문했다고 표시하고, 해당 위치의 식량 값을 변수에 저장합니다.
4. 현재 위치에서 상하좌우 네 방향으로 DFS를 재귀적으로 호출하여 연결된 땅을 탐색합니다. 각 방향에서 반환된 식량 값을 현재 위치의 식량 값에 더합니다.
5. 모든 방향에 대한 탐색이 완료되면, 현재 위치를 기준으로 연결된 땅의 총 식량 합계를 반환합니다.
6. 지도의 모든 위치에 대해 탐색을 진행하면서, 아직 방문하지 않은 땅에서 DFS를 호출하고 반환된 무인도의 식량 합계를 결과 배열에 추가합니다.
7. 모든 탐색이 완료되면, 결과 배열을 확인합니다. 배열이 비어있다면 무인도가 없는 경우이므로 [-1]을 반환하고, 그렇지 않으면 배열을 오름차순으로 정렬하여 반환합니다.

이러한 지도를 탐색하면서 연결된 땅의 식량 값을 합산하여 각 무인도에서 최대로 머물 수 있는 일수를 계산하는 것이 목표입니다...

 

시도

1차 시도  (성공)

function solution(maps) {
	// 지도의 세로 길이
	const rows = maps.length;
	// 지도의 가로 길이
	const cols = maps[0].length;
	// 방문 여부를 저장할 2차원 배열
	const visited = [];
	// 각 무인도의 식량 합계를 저장할 배열
	const result = [];
	// 방문 배열 초기화 (모든 위치를 false로 설정)
	for (let i = 0; i < rows; i++) {
		visited[i] = [];
		for (let j = 0; j < cols; j++) {
			visited[i][j] = false;
		}
	}
	// 무인도 탐색 함수 정의
	function dfs(x, y) {
		// 현재 위치가 유효한지 확인
		// 1. 지도 범위를 벗어나는 경우
		if (x < 0 || x >= rows || y < 0 || y >= cols) {
			return 0;
		}
		// 2. 이미 방문한 경우
		if (visited[x][y]) {
			return 0;
		}
		// 3. 바다('X')인 경우
		if (maps[x][y] === "X") {
			return 0;
		}
		// 현재 위치를 방문했다고 표시
		visited[x][y] = true;

		// 현재 위치의 식량 값을 정수로 변환하여 저장
		let foodSum = parseInt(maps[x][y]);
		// 상하좌우 네 방향에 대해 재귀적으로 탐색 수행
		// 각 방향의 결과를 현재 위치의 식량 값에 더함
		foodSum += dfs(x - 1, y); // 위쪽 탐색
		foodSum += dfs(x + 1, y); // 아래쪽 탐색
		foodSum += dfs(x, y - 1); // 왼쪽 탐색
		foodSum += dfs(x, y + 1); // 오른쪽 탐색
		// 현재 위치와 연결된 모든 땅의 식량 합계 반환
		return foodSum;
	}
	// 지도의 모든 위치에 대해 반복
	for (let i = 0; i < rows; i++) {
		for (let j = 0; j < cols; j++) {
			// 아직 방문하지 않았고, 땅인 경우에만 무인도 탐색 수행
			if (!visited[i][j] && maps[i][j] !== "X") {
				// 탐색 결과(무인도의 총 식량 값)를 결과 배열에 추가
				result.push(dfs(i, j));
			}
		}
	}
	// 결과 처리
	// 무인도가 하나도 없는 경우
	if (result.length === 0) {
		return [-1];
	} else {
		// 무인도가 하나 이상 있는 경우, 식량 합계를 오름차순으로 정렬하여 반환
		return result.sort((a, b) => a - b);
	}
}

DFS 알고리즘을 사용하여 연결된 땅을 탐색하고, 방문 여부를 저장하는 2차원 배열을 사용합니다. 지도의 각 위치를 탐색하면서 아직 방문하지 않은 땅을 발견하면 해당 위치에서 DFS를 시작하여 연결된 땅의 식량 값을 합산합니다. 모든 탐색이 완료되면 각 무인도의 식량 합계를 오름차순으로 정렬하여 반환하거나, 무인도가 없는 경우 [-1]을 반환합니다.

1. 지도의 세로 길이(rows)와 가로 길이(cols)를 구합니다.
2. 방문 여부를 저장할 2차원 배열(visited)을 선언하고, 모든 위치를 false로 초기화합니다.
3. 각 무인도의 식량 합계를 저장할 배열(result)을 선언합니다.
4. dfs 함수는 DFS를 수행하는 재귀 함수입니다. 현재 위치(x, y)를 기준으로 탐색을 진행합니다.
   1. 현재 위치가 지도 범위를 벗어나거나, 이미 방문한 위치이거나, 바다('X')인 경우 0을 반환하고 탐색을 종료합니다.
   2. 현재 위치를 방문했다고 표시합니다.
   3. 현재 위치의 식량 값을 정수로 변환하여 foodSum 변수에 저장합니다.
   4. 상하좌우 네 방향에 대해 재귀적으로 dfs 함수를 호출하고, 반환된 값을 foodSum에 더합니다.
   5. 현재 위치와 연결된 모든 땅의 식량 합계인 foodSum을 반환합니다.
5. 지도의 모든 위치에 대해 반복문을 수행합니다. 아직 방문하지 않았고 땅인 경우에만 dfs 함수를 호출하여 무인도 탐색을 수행하고, 탐색 결과(무인도의 총 식량 값)를 result 배열에 추가합니다.
6. 탐색이 완료된 후, result 배열을 확인합니다.
   1. 배열의 길이가 0이면 무인도가 없는 경우이므로 [-1]을 반환합니다.
   2. 그렇지 않으면 result 배열을 오름차순으로 정렬하여 반환합니다.

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(rows * cols)
  • DFS 탐색은 지도의 각 위치를 최대 한 번씩 방문하므로 시간 복잡도는 지도의 크기에 비례합니다.
• 공간 복잡도: O(rows * cols)
  • 방문 여부를 저장하는 visited 배열의 크기가 지도의 크기와 동일하므로 공간 복잡도는 O(rows * cols)입니다.

 

2차 시도 (성공)

function solution(maps) {
	// 지도의 세로 길이
	const rows = maps.length;
	// 지도의 가로 길이
	const cols = maps[0].length;
	// 방문 여부를 체크할 2차원 배열 초기화 (모두 false로 설정)
	const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
	// 각 무인도의 식량 합계를 저장할 배열
	const result = [];
	// 깊이 우선 탐색(DFS) 함수 정의
	function dfs(x, y) {
		// 현재 위치가 유효한지 확인
		// 1. 지도 범위를 벗어나는 경우
		// 2. 이미 방문한 경우
		// 3. 바다('X')인 경우
		// 위 세 경우 중 하나라도 해당되면 0을 반환하고 탐색 종료
		if (x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || maps[x][y] === "X") {
			return 0;
		}
		// 현재 위치를 방문했다고 표시
		visited[x][y] = true;

		// 현재 위치의 식량 값을 정수로 변환하여 저장
		let sum = parseInt(maps[x][y]);
		// 상하좌우 네 방향에 대해 재귀적으로 DFS 수행
		// 각 방향의 결과를 현재 위치의 식량 값에 더함
		sum += dfs(x - 1, y); // 위쪽 탐색
		sum += dfs(x + 1, y); // 아래쪽 탐색
		sum += dfs(x, y - 1); // 왼쪽 탐색
		sum += dfs(x, y + 1); // 오른쪽 탐색
		// 현재 위치와 연결된 모든 땅의 식량 합계 반환
		return sum;
	}
	// 지도의 모든 위치에 대해 반복
	for (let i = 0; i < rows; i++) {
		for (let j = 0; j < cols; j++) {
			// 아직 방문하지 않았고, 땅인 경우에만 DFS 수행
			if (!visited[i][j] && maps[i][j] !== "X") {
				// DFS 결과(무인도의 총 식량 값)를 결과 배열에 추가
				result.push(dfs(i, j));
			}
		}
	}
	// 결과 처리
	// 무인도가 하나라도 있으면 식량 합계를 오름차순으로 정렬하여 반환
	// 무인도가 없으면 [-1] 반환
	return result.length > 0 ? result.sort((a, b) => a - b) : [-1];
}

두 번째 코드는 첫 번째 코드와 동일한 문제를 해결하지만, 코드의 가독성과 간결성을 개선하였습니다. Array.from과 fill 메서드를 사용하여 방문 배열을 초기화하고, DFS 함수 내에서 현재 위치의 유효성 검사를 한 번에 처리하도록 조건문을 수정하였습니다. 또한, 결과 반환 부분을 삼항 연산자를 사용하여 한 줄로 작성하였습니다.

1. visited 배열 초기화를 Array.from과 fill 메서드를 사용하여 한 줄로 작성하였습니다.
   1. Array.from은 배열 크기를 지정하고 초기 값을 설정할 수 있는 메서드입니다. 첫 번째 인자로 배열의 길이를 지정하고, 두 번째 인자로 각 요소를 초기화하는 함수를 전달합니다.
   2. fill 메서드는 배열의 시작 인덱스부터 끝 인덱스까지 지정된 값으로 채웁니다. 여기서는 false로 채워 모든 위치를 방문하지 않은 상태로 초기화합니다.
2. dfs 함수 내에서 현재 위치의 유효성 검사를 한 번에 처리하도록 조건문을 수정하였습니다.
   1. 현재 위치가 지도 범위를 벗어나거나, 이미 방문한 위치이거나, 바다('X')인 경우 중 하나라도 해당되면 0을 반환하고 탐색을 종료합니다.
3. 결과 반환 부분을 삼항 연산자를 사용하여 한 줄로 작성하였습니다.
   1. result 배열의 길이가 0보다 크면 무인도가 하나 이상 있는 경우이므로, 배열을 오름차순으로 정렬하여 반환합니다.
   2. 그렇지 않으면 무인도가 없는 경우이므로 [-1]을 반환합니다.

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(rows * cols)
  • DFS 탐색은 지도의 각 위치를 최대 한 번씩 방문하므로 시간 복잡도는 지도의 크기에 비례합니다.
• 공간 복잡도: O(rows * cols)
  • 방문 여부를 저장하는 visited 배열의 크기가 지도의 크기와 동일하므로 공간 복잡도는 O(rows * cols)입니다.