[TIL] DFS & BFS 알고리즘 공부

알고리즘 공부

DFS & BFS

토마토

https://www.acmicpc.net/problem/7576

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [nums, ...map] = input
const [m, n] = nums.split(' ').map((x) => +x)
const tomato = map.map((x) => x.split(' ')).map((x) => x.map((x) => +x))

const queue = []
let countZero = 0
for (let y = 0; y < n; y++) {
	for (let x = 0; x < m; x++) {
		if (tomato[y][x] === 1) {
			queue.push(y)
			queue.push(x)
			queue.push(0)
		} else if (tomato[y][x] === 0) {
			countZero++
		}
	}
}

const dy = [0, 0, 1, -1]
const dx = [1, -1, 0, 0]

let index = 0
let minDay = 0
while (index < queue.length) {
	const y = queue[index++]
	const x = queue[index++]
	const day = queue[index++]

	for (let i = 0; i < 4; i++) {
		const new_y = y + dy[i]
		const new_x = x + dx[i]

		if (
			new_y < 0 ||
			new_y >= n ||
			new_x < 0 ||
			new_x >= m ||
			tomato[new_y][new_x] !== 0
		)
			continue

		tomato[new_y][new_x] = 1

		queue.push(new_y)
		queue.push(new_x)
		queue.push(day + 1)

		minDay = minDay < day + 1 ? day + 1 : minDay

		countZero--
	}
}
console.log(countZero === 0 ? minDay : -1)

유기농 배추

https://www.acmicpc.net/problem/1012

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [numTest, ...test] = input
let index = 0
const dx = [0, 0, 1, -1]
const dy = [1, -1, 0, 0]

let answer = ''
for (let i = 0; i < numTest; i++) {
	const [m, n, k] = test[index++].split(' ').map((x) => +x)
	const locations = []
	for (let j = 0; j < k; j++) {
		locations.push(test[index++].split(' ').map((x) => +x))
	}
	const map = Array.from(Array(m), () => Array(n).fill(0))
	for (const location of locations) {
		const x = location[0]
		const y = location[1]
		map[x][y] = 1
	}
    let count = 0
	for (let x = 0; x < m; x++) {
		for (let y = 0; y < n; y++) {
			if (map[x][y] === 1) {
                count++
				const toVisit = []
				toVisit.push([x, y])
				while (toVisit.length) {
					const node = toVisit.pop()
					const a = node[0]
					const b = node[1]
					map[a][b] = 0
					for (let i = 0; i < 4; i++) {
						const newx = a + dx[i]
						const newy = b + dy[i]
						if (
							newx < 0 ||
							newx >= m ||
							newy < 0 ||
							newy >= n ||
							map[newx][newy] === 0
						)
							continue
						toVisit.push([newx, newy])
					}
				}
			}
		}
	}
    answer += count + '\n'
}
console.log(answer)