성빈킴 블로그

백준 2667 단지번호 붙이기 node.js

백준 2667 단지번호 붙이기 node.js

2023-8-20

풀이전략

모든 요소로 DFS를 수행하는데, 행렬에서 1이면서 visit하지 않은것만 수행. 수행횟수 -> 단지 갯수 재귀 호출 횟수 -> answer배열에 추가후 초기화 출력한다!

풀이

const [N, ...mLines] = `7 0110100 0110101 1110101 0000111 0100000 0111110 0111000` .trim() .split('\n'); const n = Number(N); const matrix = mLines.map((l) => l.split('').map(Number)); const visited = Array.from({ length: n }, () => Array(n).fill(0)); let ComplexCount = 0; const householdes = []; let houseCount = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (!visited[i][j] && matrix[i][j]) { ComplexCount++; dfs(i, j); householdes.push(houseCount); houseCount = 0; } } } console.log(ComplexCount); console.log(householdes.sort((a, b) => a - b).join('\n')); function dfs(row, col) { houseCount++; visited[row][col] = 1; // 들어온 노드에 상하좌우에 연결된것 중 방문하지 않은것 들을 dfs 호출할것. if (row && !visited[row - 1][col]) { matrix[row - 1][col] && dfs(row - 1, col); } if (row < n - 1 && !visited[row + 1][col]) { matrix[row + 1][col] && dfs(row + 1, col); } if (col < n - 1 && !visited[row][col + 1]) { matrix[row][col + 1] && dfs(row, col + 1); } if (col && !visited[row][col - 1]) { matrix[row][col - 1] && dfs(row, col - 1); } }

풀고나서

DFS가 많이 익숙해진 느낌입니다.

단순연결리스트 역순 뒤집기

단순연결리스트 역순 뒤집기

백준 4963 섬의개수 node.js

백준 4963 섬의개수 node.js