[TIL]Typescript 강의, DFS & BFS 알고리즘

Typescript 강의 듣기

https://www.inflearn.com/course/%ED%83%80%EC%9E%85%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%9E%85%EB%AC%B8

DFS & BFS 알고리즘 문제 풀이

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

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

const [num, ...test] = input
const [n, m, v] = num.split(' ').map((x) => +x)
const graph = test
	.map((x) => x.split(' '))
	.reduce((graph, pair) => {
		graph[pair[0]]
			? graph[pair[0]].push(+pair[1])
			: (graph[pair[0]] = [+pair[1]])
		graph[pair[1]]
			? graph[pair[1]].push(+pair[0])
			: (graph[pair[1]] = [+pair[0]])
		return graph
	}, {})

// DFS
let resultDFS = ''
let toVisitDFS = [v]
const visitedDFS = []
while (toVisitDFS.length) {
	const node = toVisitDFS.pop()
	if (!node) continue
	if (visitedDFS.includes(node)) continue
	resultDFS += node + ' '
	visitedDFS.push(node)
	if (graph[node]) {
		graph[node].sort((a, b) => b - a)
		toVisitDFS = [...toVisitDFS, ...graph[node]]
	}
}
console.log(resultDFS.trim())

// BFS
let resultBFS = ''
let toVisitBFS = [v]
const visitedBFS = []
while (toVisitBFS.length) {
	const node = toVisitBFS.shift()
	if (!node) continue
	if (visitedBFS.includes(node)) continue
	resultBFS += node + ' '
	visitedBFS.push(node)
	if (graph[node]) {
		graph[node].sort((a, b) => a - b)
		toVisitBFS = [, ...toVisitBFS, ...graph[node]]
	}
}
console.log(resultBFS.trim())

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

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

const [n, m, ...list] = input

const graph = list
	.map((x) => x.split(' '))
	.reduce((graph, pair) => {
		graph[pair[0]]
			? graph[pair[0]].push(pair[1])
			: (graph[pair[0]] = [pair[1]])
		graph[pair[1]]
			? graph[pair[1]].push(pair[0])
			: (graph[pair[1]] = [pair[0]])
		return graph
	}, {})

let toVisit = ['1']
const visited = []
while (toVisit.length) {
	const node = toVisit.pop()
	if (visited.includes(node)) continue
	visited.push(node)
	toVisit = [...graph[node], ...toVisit]
}

console.log(visited.length - 1)

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

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

const [n, ...list] = input
let map = list.map((x) => x.split(''))

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

let count = 0
const housecounts = []
for (let y = 0; y < +n; y++) {
	for (let x = 0; x < +n; x++) {
		if (map[y][x] === '1') {
			count++
			let toVisit = [[y, x]]
			let housecount = 0
			while (toVisit.length) {
				const node = toVisit.pop()
				const nodey = node[0]
				const nodex = node[1]
                if (map[nodey][nodex] === '1') {
                    map[nodey][nodex] = '0'
                    housecount++
                }
				for (let i = 0; i < 4; i++) {
					const newy = nodey + dy[i]
					const newx = nodex + dx[i]
					if (
						newy < 0 ||
						newy >= +n ||
						newx < 0 ||
						newx >= +n ||
						map[newy][newx] === '0'
					) {
						continue
					}
					toVisit.push([newy, newx])
				}
			}
			housecounts.push(housecount)
		}
	}
}
housecounts.sort((a,b)=>a-b)
console.log(count)
console.log(housecounts.join('\n'))