package main
import (
"bufio"
"fmt"
"os"
)
type XY struct {
x int
y int
}
var dx = []int{-1, 0, 1, 0}
var dy = []int{0, 1, 0, -1}
var w = bufio.NewWriter(os.Stdout)
var r = bufio.NewReader(os.Stdin)
var N, M int
var board, board2 [10][10]int
func pad(x, y, dir int) {
dir %= 4
for 1 == 1 {
x += dx[dir]
y += dy[dir]
if 0 > x || x >= N || 0 > y || y >= M || board2[x][y] == 6 { // reach the wall
break
}
if board2[x][y] != 0 { // there is a cctv, able to get through
continue
}
board2[x][y] = 7
}
}
func main() {
prev := 0
var cctv []XY = make([]XY, 0, 8)
defer w.Flush()
fmt.Fscan(r, &N, &M)
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
fmt.Fscan(r, &board[i][j])
if board[i][j] == 0 {
prev += 11
} else if board[i][j] > 0 && board[i][j] < 6 {
cctv = append(cctv, XY{i, j})
}
}
}
// fmt.Fprintln(w, cctv)
// fmt.Fprint(w, board)
for k := 0; k < 1<<(2*len(cctv)); k++ { // 4진수로 모든 방향 탐색
ans := 0
kk := k
for i := range board {
for j, value := range board[i] {
board2[i][j] = value
}
}
for c := 0; c < len(cctv); c++ { // 4진수 각 자리별로 cctv 의 방향을 나타냄
dir := kk % 4
kk /= 4
x := cctv[c].x
y := cctv[c].y
switch board2[x][y] {
case 1:
pad(x, y, dir)
case 2:
pad(x, y, dir)
pad(x, y, dir+2)
case 3:
pad(x, y, dir)
pad(x, y, dir+1)
case 4:
pad(x, y, dir)
pad(x, y, dir+1)
pad(x, y, dir+2)
case 5:
pad(x, y, dir)
pad(x, y, dir+1)
pad(x, y, dir+2)
pad(x, y, dir+3)
}
}
// fmt.Fprintln(w, board2)
for i := 0; i < N; i++ { // 0 개수 카운트
for j := 0; j < M; j++ {
if board2[i][j] == 0 {
ans += 1
}
}
}
if ans < prev {
prev = ans
ans = prev
}
}
fmt.Fprintln(w, prev)
}먼저, ans 값을 빈칸 갯수 (0) 으로 설정해놓는다.
입력받으면서 cctv 좌표를 배열에 넣는다.
$4^k (k=cctv)$ 만큼 반복문을 돌며,
각 자리수가 방향을 나타내게 한다
ex : ) cctv 개수 : 4
0000
0001
0002
0003
0010
0011
...
3333각 cctv 의 방향대로 board2 에 7로 채운다
벽은 통과할 수 없으므로 break 하고
cctv 는 통과할 수 있으니 continue 해준다
그동안 배웠던 알고리즘 활용하는거는 약간 어려워서 바킹독님 강의 많이 참고했다. 백트래킹 대신 4진수를 쓰는 아이디어가 신기했다
