1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 아이스크림의 개수를 구하라 - 주어진 자료는 무엇인가?
- N x M 크기의 얼음틀
- ices = 얼음틀의 형태가 배열로 주어진다.
2. 계획
dfs를 어떻게 구현할 수 있을지 생각이 나지 않아서 해당 책에 나와있는 파이썬 예제를 자바스크립트로 변경해서 따라서 풀었다.,,
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
const solution = (N, M, ices) => {
function dfs(x, y) {
if (x <= -1 || x >= N || y <= -1 || y >= M) {
return false;
}
if (ices[x][y] === 0) {
ices[x][y] = 1;
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
return true;
}
return false;
}
let answer = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (dfs(i, j)) {
answer += 1;
}
}
}
return answer
};
test('dfs', () => {
expect(solution(15, 14, [
[0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
])).toEqual(8);
});
4. 반성
dfs, bfs 공부를 더 하고 관련 문제들을 더 풀어봐야겠다.
'코테연습' 카테고리의 다른 글
102. 이것이 코딩 테스트다 7장 : 떡볶이 떡 만들기 Javascript (0) | 2022.09.02 |
---|---|
101. 이것이 코딩 테스트다 7장 : 부품 찾기 Javascript (0) | 2022.09.02 |
99. 이것이 코딩 테스트다 6장 : 두 배열의 원소 교체 Javascript (0) | 2022.09.01 |
98. 이것이 코딩 테스트다 6장 : 성적이 낮은 순서로 학생 출력하기 Javascript (0) | 2022.09.01 |
97. 이것이 코딩 테스트다 6장 : 위에서 아래로 Javascript (0) | 2022.09.01 |
댓글