프로그래머스: 석유 시추
석유 시추
석유 덩어리의 위치를 나타내는 이중 배열 land가 주어졌을 때, 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량 return하기
제한 조건
1 ≤land.length≤ 500
1 ≤land[0].length≤ 500문제 풀이 조건
land[i][j]는 0 또는 1이며, 1은 석유를 의미함.
시추기는 땅에 수직으로 설치하며, 열 하나를 관통하여 최대 깊이(land.length)에 닿음.
알고리즘 구상하기
석유 덩어리의 위치와 양을 파악하는 방법 생각하기
우선, 문제에서 요구하는 ‘가장 많은 석유량’을 구하기 위해 거쳐야 할 단계를 정리했다.
- 각 석유 덩어리의 위치를 찾아, 0으로 둘러싸인 한 덩어리를 완성한다.
- 석유 덩어리의 x좌표(column)를 기록한다.
- 석유 덩어리의 규모가 확장될 때마다 1씩 카운팅 한다.
- 석유 덩어리가 완성되면, 카운팅한 횟수를 이용해 총 석유량을 구한다.
1번에서 얻은 석유 덩어리들의 위치를 이용해, 각 x좌표에 걸치고 있는 석유 덩어리들의 규모를 파악한다.
석유덩어리들의 총 규모가 가장 큰 x좌표의 석유량이 정답이 된다.
구현방법: DFS
1차 시도: 재귀 함수를 이용해 석유의 위치 파악하기
석유 덩어리의 위치를 찾기 위해 DFS를 이용하였다. DFS를 이용하면 방문 여부를 판별하여 서로 연결된 node를 데이터화 할 수 있기 때문이다.
우선, 가장 가독성이 좋다고 생각하는 재귀함수를 이용해 DFS를 구현했다. 현재 index에서 2차원으로 상, 하, 좌, 우로 이동하여 석유의 범위를 파악하도록 함수를 중첩 호출했다. 이중 배열의 요소 값이 0이거나 배열 범위를 벗어나는 경우, 중첩함수는 종료된다.
최종적으로 호출 stack의 최상단 실행 컨택스트가 실행되면 완성된 석유 덩어리(oilGroup)을 반환하도록 구성했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const findOil = (y, x, oilGroup) => {
if (y < 0 || x < 0 || y >= totalRow || x >= totalColumn) {
return [];
}
if (land[y][x] === 0 || visited[y][x]) {
return [];
}
visited[y][x] = true;
oilGroup.push(x);
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
for (const [moveY, moveX] of move) {
const nextY = moveY + y;
const nextX = moveX + x;
findOil(nextY, nextX, oilGroup);
}
return oilGroup;
};
모든 석유 덩어리들의 row 범위를 파악하면, 이 데이터를 순회하며 각 row에 적재된 oil의 양을 계산하도록 반복문을 실행했다.
하나의 석유덩어리에 같은 row가 여러 개 존재할 수 있기 때문에 oil의 양을 중복 가산하지 않도록 Set 자료구조를 이용했다.
1
2
3
4
5
6
7
8
9
10
const oilAmountList = Array.from({ length: totalColumn }, () => 0);
oilGroupList.forEach((group) => {
const targetColumns = new Set(group);
const oilAmount = group.length;
for (const column of targetColumns) {
oilAmountList[column] += oilAmount;
}
});
return Math.max(...oilAmountList);
이를 토대로 구현한 1차 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function solution(land) {
const totalRow = land.length;
const totalColumn = land[0].length;
const visited = Array.from({ length: totalRow }, () =>
Array.from({ length: totalColumn })
);
const oilGroupList = [];
const findOil = (y, x, oilGroup) => {
if (y < 0 || x < 0 || y >= totalRow || x >= totalColumn) {
return [];
}
if (land[y][x] === 0 || visited[y][x]) {
return [];
}
visited[y][x] = true;
oilGroup.push(x);
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
for (const [moveY, moveX] of move) {
const nextY = moveY + y;
const nextX = moveX + x;
findOil(nextY, nextX, oilGroup);
}
return oilGroup;
};
for (let row = 0; row < totalRow; row += 1) {
for (let column = 0; column < totalColumn; column += 1) {
const oilGroup = findOil(row, column, []);
if (oilGroup.length > 0) {
oilGroupList.push(oilGroup);
}
}
}
const oilAmountList = Array.from({ length: totalColumn }, () => 0);
oilGroupList.forEach((group) => {
const targetColumns = new Set(group);
const oilAmount = group.length;
for (const column of targetColumns) {
oilAmountList[column] += oilAmount;
}
});
return Math.max(...oilAmountList);
}
그러나 위 코드는 효율성 검사를 통과하지 못하였다. 이에 따라, 위 코드에서 효율성을 개선할 수 있는 방법을 고민했다.
2차 시도: 반복문을 이용한 DFS
재귀함수로 구현한 코드가 실패했을때 내가 가장 먼저 사용하는 방법은 반복문으로 수정하는 것이다. 특히 자바스크립트의 경우, 싱글 스레드이기 때문에 재귀함수로 인해 오버헤드가 발생할 수 있다.
이에 따라, 다음과 같이 재귀함수를 while 반복문으로 수정했다.
좌표를 담은 stack 데이터를 배열로 생성하고 stack의 길이가 0이 될 때까지 반복문을 수행하게 했다. 기존에는 재귀함수 인자로 주어졌던 좌표가, stack에 담긴 데이터로 변경된 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const findOil = (startY, startX) => {
const oilGroup = [];
const stack = [[startY, startX]];
while (stack.length > 0) {
const [y, x] = stack.pop();
if (
y < 0 ||
x < 0 ||
y >= totalRow ||
x >= totalColumn ||
land[y][x] === 0 ||
visited[y][x]
) {
continue;
}
visited[y][x] = true;
oilGroup.push(x);
const moves = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
for (const [moveY, moveX] of moves) {
stack.push([y + moveY, x + moveX]);
}
}
return oilGroup;
};
for (let row = 0; row < totalRow; row += 1) {
for (let column = 0; column < totalColumn; column += 1) {
if (land[row][column] === 1 && !visited[row][column]) {
const oilGroup = findOil(row, column);
if (oilGroup.length > 0) {
oilGroupList.push(oilGroup);
}
}
}
}
그러나 반복문으로 수정한 코드도 효율성 검사를 통과하지 못했다. 이에 따라, 두 번째로 복잡한 연산이나 지나친 반복문을 찾아 수정하는 작업을 했다.
3차 시도: 불필요한 반복문 줄이기
3번째 수정에서 눈에 띈 것은 무수한 반복문이었다.
dfs 알고리즘, 좌표를 stack에 push하는 코드, 각 row별 석유량을 계산하는 코드에 반복문이 사용되고 있었다. 심지어 가장 많은 석유량을 계산할 때 Math.max() 메서드를 이용했기 때문에, 마지막에 마지막까지 데이터를 순회하고 있었다.
이에 따라, 동일한 데이터를 여러 번 순회하는 알고리즘을 개선했다.
기존에는 2차원 배열에서 상, 하, 좌, 우로 이동하는 알고리즘을 구현하기 위해 반복문을 사용했었다. 이 반복문을 제거하고 직접 이동할 좌표들을 일괄적으로 stack에 push하도록 수정했다. 이는, stack에 push할 좌표가 4개 밖에 없기에 가능한 개선안이었다.
기존에는 row별 석유량을 배열로 데이터화한 후, 이를 다시 순회해 가장 많은 석유량을 계산했었다.
그러나 이번에는 row별 석유량을 계산하는 로직 내부에 가장 많은 석유량을 업데이트하는 코드도 추가했다. 즉, 별도의 로직으로 분리되어 두 번의 반복을 수행해야 했던 코드를 하나로 통합했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function solution(land) {
const totalRow = land.length;
const totalColumn = land[0].length;
const visited = Array.from({ length: totalRow }, () =>
Array.from({ length: totalColumn }, () => false)
);
const oilGroupList = [];
const findOil = (startY, startX) => {
// ...
stack.push([y, x + 1], [y, x - 1], [y + 1, x], [y - 1, x]); // 직접 stack에 push
// ...
};
const oilAmountList = Array.from({ length: totalColumn }, () => 0);
let answer = 0;
for (let row = 0; row < totalRow; row += 1) {
for (let column = 0; column <= totalColumn - 1; column += 1) {
// ...
if (oilAmount > 0) {
const targetColumns = new Set(oilGroup);
for (const column of targetColumns) {
oilAmountList[column] += oilAmount;
answer = Math.max(oilAmountList[column], answer); // 가장 많은 석유량 업데이트
}
}
}
}
return answer;
}
이와 같은 개선을 거친 끝에, 효율성 검사를 통과한 아래의 최종 코드를 완성할 수 있었다.
[JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function solution(land) {
const totalRow = land.length;
const totalColumn = land[0].length;
const visited = Array.from({ length: totalRow }, () =>
Array.from({ length: totalColumn }, () => false)
);
const oilGroupList = [];
const findOil = (startY, startX) => {
const oilGroup = [];
const stack = [[startY, startX]];
while (stack.length > 0) {
const [y, x] = stack.pop();
if (
y >= 0 &&
x >= 0 &&
y < totalRow &&
x < totalColumn &&
land[y][x] === 1 &&
!visited[y][x]
) {
visited[y][x] = true;
oilGroup.push(x);
stack.push([y, x + 1], [y, x - 1], [y + 1, x], [y - 1, x]);
}
}
return oilGroup;
};
const oilAmountList = Array.from({ length: totalColumn }, () => 0);
let answer = 0;
for (let row = 0; row < totalRow; row += 1) {
for (let column = 0; column <= totalColumn - 1; column += 1) {
if (land[row][column] === 1 && !visited[row][column]) {
const oilGroup = findOil(row, column);
const oilAmount = oilGroup.length;
if (oilAmount > 0) {
const targetColumns = new Set(oilGroup);
for (const column of targetColumns) {
oilAmountList[column] += oilAmount;
answer = Math.max(oilAmountList[column], answer);
}
}
}
}
}
return answer;
}