알고리즘
백준 단지번호 붙이기(Go)
PudgeKim
2021. 4. 11. 14:19
문제 링크: www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
전형적인 BFS(DFS로도 풀이가능)문제입니다. 마지막에 정렬 후에 출력해야 하는 것에 주의해야합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
)
type Item struct {
x int
y int
cnt int
}
type Queue []*Item
func (q *Queue) Push(item *Item) {
*q = append(*q, item)
}
func (q *Queue) Pop() *Item {
old := *q
n := len(old)
popped := old[0]
old[0] = nil
*q = old[1:n]
return popped
}
func GetIntSlice(input string, s *[]int, n int) {
for i:=0; i<n; i++ {
num, _ := strconv.Atoi(string(input[i]))
*s = append(*s, num)
}
}
func Bfs(sx, sy, n, color int, board, visited [][]int) int {
var dx = []int{0, 0, -1, 1}
var dy = []int{-1, 1, 0, 0}
q := Queue{}
q.Push(&Item{sx, sy, 0})
res := 1 // 단지 몇개인지
visited[sx][sy] = 1
for {
if len(q) == 0 { break }
item := q.Pop()
x, y, cnt := item.x, item.y, item.cnt
for i:=0; i<4; i++ {
nx, ny := x+dx[i], y+dy[i]
if 0<=nx && nx<n && 0<=ny && ny<n && visited[nx][ny]==0{
if board[nx][ny] == 1 {
visited[nx][ny] = 1
board[nx][ny] = color
res += 1
q.Push(&Item{nx, ny, cnt+1})
}
}
}
}
return res
}
func main() {
var n int
fmt.Scanln(&n)
scanner := bufio.NewScanner(os.Stdin)
board := make([][]int, n)
for i:=0; i<n; i++ {
scanner.Scan()
input := scanner.Text()
GetIntSlice(input, &board[i], n)
}
visited := make([][]int, n)
for i:=0; i<n; i++ {
for j:=0; j<n; j++ {
visited[i] = append(visited[i], 0)
}
}
answer := 0
color := 2
var resList []int
for i:=0; i<n; i++ {
for j:=0; j<n; j++ {
if board[i][j] == 1 {
res := Bfs(i, j, n, color, board, visited)
resList = append(resList, res)
answer += 1
color += 1
}
}
}
sort.Slice(resList, func(i, j int) bool { return resList[i] < resList[j]})
fmt.Println(answer)
for _, val := range resList {
fmt.Println(val)
}
}
|
cs |