-
문제
N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0 이고 칸막이가 존재하는 부분은 1이다. 즉, 0으로 연결된 부분이 얼음 한 덩이가 얼려져 나오는 것이다. 구멍이 뚫려 있는 부분 끼리 상, 하, 좌, 우로 붙어 있는 경우가 서로 연결된 경우가 된다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
예시
예시로 아래와 같은 얼음판의 경우를 보자.
00110000111111100000출력
3
How to Solve ?
최초에 구멍이 뚫려있는 (=0) 을 만나면, DFS를 통해 0 주변(상,하,좌,우)에 모두 음료수를 붓는 방식으로 문제를 해결한다.
즉, 0을 만나서 DFS를 수행 할 때 주변에도 0이 있다면 한번에 처리를 하여 1개의 아이스크림으로 간주한다.
function DFS(x, y) {if (x <= -1 || x >= N || y <= -1 || y >= N) {return false;}if (iced[x][y] === 0) {iced[x][y] = 1;DFS(x - 1, y);DFS(x, y - 1);DFS(x + 1, y);DFS(x, y + 1);return true;}return false;}function solution() {let answer = 0;for (let i = 0; i < N; i++) {for (let j = 0; j < K; j++) {if (DFS(i, j) === true) {answer += 1;}}}return answer;}let [N, K] = [3, 3];const iced = [[0, 0, 1],[0, 1, 0],[1, 0, 1],];console.log(solution());'PS > 기타' 카테고리의 다른 글
[DP] 개미전사 ( by using JavaScript ) (0) 2021.06.02 [시뮬레이션] 게임 개발 ( by using JavaScript ) (0) 2021.06.02