[백준] 2667번: - 단지번호붙이기 kotlin
문제
https://www.acmicpc.net/problem/2667
풀이
- (0,0) 부터 차례대로 "1"인 값 탐색
- 방문하지 않은 곳이고 "1" 값이라면 DFS 실행
- 현재 방문한 곳은 체크하고, 상하좌우 방문하지 않았고, "1" 값이라면 DFS 실행
- DFS 의 반환 값은 방문한 개수이므로 이를 누적시킨다.
val dx = listOf(0, 1, 0, -1)
val dy = listOf(1, 0, -1, 0)
fun dfs(graph: MutableList<List<String>>, visited: Array<Array<Boolean>>, x: Int, y: Int, n: Int): Int {
visited[x][y] = true
var count = 1
for (i in 0 until 4) {
val nx = x + dx[i]
val ny = y + dy[i]
if (nx in (0 until n) && ny in (0 until n) && !visited[nx][ny] && graph[nx][ny] == "1") {
count += dfs(graph, visited, nx, ny, n)
}
}
return count
}
fun main() {
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val n = br.readLine().toInt()
val graph = mutableListOf<List<String>>()
repeat(n) {
val houses = br.readLine().toString().split("").filter { it.isNotBlank() }
graph.add(houses)
}
val visited = Array(n + 1) { Array(n + 1) { false } }
val answer = mutableListOf<Int>()
for (i in 0 until n) {
for (j in 0 until n) {
if (!visited[i][j] && graph[i][j] == "1") {
answer.add(dfs(graph, visited, i, j, n))
}
}
}
bw.write("${answer.size}\n")
answer.sort()
answer.forEach {
bw.write("$it\n")
}
br.close()
bw.close()
}
더 좋은 방법 있으면 댓글 달아주세요!!!
Author And Source
이 문제에 관하여([백준] 2667번: - 단지번호붙이기 kotlin), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-2667번-단지번호붙이기-kotlin저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)