문제
- 한 변의 길이가 N인 정사각형 모양의 마을 M을 만드는 중이다.
- 마을의 모든 칸에는 건물이 하나씩 있고 r번째 행, c번째 열에해당하는 칸에는 정수 Mrc가 적혀있다.
- Mrc는 해당 칸에 있는 건물의 유형에 해당한다.
- 건물의 유형이 동일하면서, 서로 상하좌우에 인접한 건물끼리는 서로 전력을 공유할 수 있다.
- 전력을 공유할 수 있는 건물의 개수가 K개 이상이면 이를 단지라고 한다.
- 플레이어는 단 하나의 발전기만 설치할 수 있다.
- 발전기는 특정 건물의 유형 하나에 해당하는 모든 단지에 전력 공급이 가능하다.
- 가장 많은 단지가 있는 건물 유형에 전력을 공급할 것인데, 건물 유형이 여러개라면 Mrc가 더 큰 건물 유형에 전력을 공급한다.
- 전력을 공급해야 할 건물의 유형 번호를 구해보자.
코드
const readline = require('readline');
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
input.push(line.trim())
}).on('close', () => {
const [N, K] = input[0].split(" ").map(Number)
const matrix = input.slice(1).map((str) => str.split(" ").map(Number))
const visited = Array.from(Array(N), () => Array(N).fill(false))
const DIR_ARR = [
[-1, 0],
[0, -1],
[0, 1],
[1, 0]
]
const score = {
}
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix.length; j++) {
// 방문하지 않았다면 시작
if (!visited[i][j]) {
const target = matrix[i][j]
let size = 1
const stack = []
stack.push([i, j])
while (stack.length) {
const [cntY, cntX] = stack.pop()
visited[cntY][cntX] = true
for (let DIR of DIR_ARR) {
const [dy, dx] = DIR
const nextY = cntY + dy
const nextX = cntX + dx
if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < N) {
if (!visited[nextY][nextX] && matrix[nextY][nextX] === target) {
visited[nextY][nextX] = true
stack.push([nextY, nextX])
size++
}
}
}
}
if (size >= K) {
score[target] = (score[target] || 0) + 1
}
}
}
}
// value를 기준으로 내림차순. value가 같다면 key를 기준으로 내림차순
const sortedScores = Object.entries(score).sort((a, b) => b[1] - a[1] || b[0] - a[0])
// sotredScores가 있다면 첫번째 key를 리턴. 아니라면 -1을 리턴
console.log(sortedScores.length ? sortedScores[0][0] : -1)
})
- 이전 발전기와 비슷한 문제라 어떤게 DFS고 어떤게 BFS인지 모르겠다.
- 행렬을 DFS나 BFS로 순회할때의 효율성 차이는 크게 나지 않을 것 같다.
- Object.entries와 sort를 이용한 내림차순 방법이 흥미로웠다. b[1] - a[1]이 0일 때 b[0] - a[0]을 한다니 약간 천재적인 발상같다. 다른 문제를 풀 때 애용해보아야겠다.
