https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
15683 : 감시 / 문제 소개
문제는 이해하기 쉬웠다. 그렇지만 코드를 구현함에 있어서 그렇진 않았다....
사무실에는 K개의 CCTV가 설치되어 있다.
CCTV는 다섯가지다.
CCTV는 90도 방향으로 회전도 가능하다.
CCTV는 CCTV를 통과할 수 있다!!!
0 1 0 2
0 0 0 0
0 0 0 0
이렇게 된다면
2가 가로 세로 방향일 때 1은 아래 방향이라하면
# 1 # 2
0 # 0 0
0 # 0 0
이렇게 CCTV를 통과할 수 있다.
하지만 벽(6)은 통과할 수 없다.
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
풀이 과정
처음에 문제를 풀 때는 우선 특정 cctv좌표에서 상 하 좌 우 cctv시야 각을 다 저장한 다음에
Greedy하게 가장 큰 값을 선택해서 문제를 풀어나갔는데 나중엔 시야각이 같은 경우에도 무저건 이전것만 선택해서 답을 틀렸다.
그리고 가장 큰 값 말고 같은 큰 값도 다음 cctv탐색을 이어나갔는데 안됐다.
음 cctv 5번째는 상하 좌우 , 4는 3방향 ... 2는 2방향 으로 작아지니까 큰값부터 탐색해가면 ? 그래도 안됐다.
반대의 경우 작은 cctv시야 방향부터 1...5까지 cctv List를 정렬 후 탐색했는데도 안됐다.
4 6
2 6 0 3 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 6 1
correct = 8 wrong = 9
3 6
0 5 5 0 2 0
0 0 2 0 0 3
0 0 0 0 0 0
correct = 2 wrong 3
이 두가지의 경우에 막혔다.
아기 상어를 풀 때 처럼 Greedy하게? 풀어나갔는데 결국엔 모든 경우를 파악해야 풀 수 있는 문제임을 알게 됬다.
특정 cctv 종류에 따라 가장 많은 시야만!!! 탐색할 수 있는 방향을 선택해 다음 cctv좌표에서의 시야각을 탐색하지 않고,
시야가 최악의 경우까지 탐색을 계속해서 이어 나간 결과 맞을 수 있었다.
코드는 그냥 모든 경우를 다 탐색해나갔다.( 아 이렇게 힘겹게 풀어나간 사람도 있구나 하는 마음으로 봐주면 감사합니다. 코드구현이 좀 부족합니다.)
음 문제를 3시간 넘게 풀었는데 지금 다시보니 case에 따라서 탐색할 방향을 direction배열에 저장해도 좋을 것 같다는 생각이.. 들었다.(음 다른분의 코드를 보니 ㅋㅋㅋㅋ큼.)
//left == 0,right == 1,up == 2,down == 3
let direction : [point] = [(-1,0),(1,0),(0,1),(0,-1)]
onCctv함수를 통해서 특정 방향(상 하 좌 우) 에 대해서 탐색할 수있는 시야를 -1로 처리를 했다.
코드 구현
import Foundation
typealias point = (x:Int,y:Int)
//left == 0,right == 1,up == 2,down == 3
let direction : [point] = [(-1,0),(1,0),(0,1),(0,-1)]
class mapInfo
{
let height : Int
let width : Int
var map : [[Int]]
var cctvList : [point]
init()
{
let hw = readLine()!.split(separator:" ").map{Int(String($0))!}
height = hw[0]
width = hw[1]
map = Array(repeating: [Int](), count: height)
cctvList = [point]()
for y in 0..<height
{
map[y] = readLine()!.split(separator:" ").map{Int(String($0))!}
for x in 0..<width
{
if map[y][x] >= 1 && map[y][x] <= 5
{
cctvList.append((x,y))
}
}
}
}
}
func onCctv(_ point : point, arrow i : Int, _ info : mapInfo,_ map : inout[[Int]]){
let (cctvX,cctvY) = (point.x,point.y)
var curX = cctvX, curY = cctvY
while true
{
curX = curX + direction[i].x
curY = curY + direction[i].y
if curX < 0 || curX > info.width - 1 || curY < 0 || curY > info.height - 1 || info.map[curY][curX] == 6
{
break
}
else if map[curY][curX] == 0
{
map[curY][curX] = -1
}
}
}
func cctvWorking(_ index : Int,_ info : mapInfo, map : [[Int]], _ ans : inout Int)
{
if index == info.cctvList.count
{
var count = 0
for y in 0..<info.height
{
for x in 0..<info.width
{
if map[y][x] == 0
{
count += 1
}
}
}
if count < ans
{
ans = count
return
}
return
}
let (cctvX,cctvY) = info.cctvList[index]
var m = map
switch map[cctvY][cctvX]
{
case 1:
for i in 0..<4
{
m = map
onCctv((cctvX,cctvY), arrow: i, info, &m)
cctvWorking(index + 1, info, map: m, &ans)
}
break;
case 2:
onCctv((cctvX,cctvY), arrow: 0, info,&m)
onCctv((cctvX,cctvY), arrow: 1, info,&m)
cctvWorking(index+1, info, map: m, &ans)
var m2 = map
onCctv((cctvX,cctvY), arrow: 2, info,&m2)
onCctv((cctvX,cctvY), arrow: 3, info,&m2)
cctvWorking(index+1, info, map: m2, &ans)
break;
case 3:
onCctv((cctvX,cctvY), arrow: 0, info, &m)
var m2 = m
onCctv((cctvX,cctvY), arrow: 2, info,&m)
cctvWorking(index+1, info, map: m, &ans)
onCctv((cctvX,cctvY), arrow: 3, info, &m2)
cctvWorking(index+1, info, map: m2, &ans)
var m3 = map
onCctv((cctvX,cctvY), arrow: 1, info,&m3)
var m4 = m3
onCctv((cctvX,cctvY), arrow: 2, info,&m3)
cctvWorking(index+1, info, map: m3, &ans)
onCctv((cctvX,cctvY), arrow: 3, info, &m4)
cctvWorking(index+1, info, map: m4, &ans)
break;
case 4:
var m2 = map
var m3 = map
var m4 = map
onCctv((cctvX,cctvY), arrow: 0, info, &m)
onCctv((cctvX,cctvY), arrow: 1, info, &m)
onCctv((cctvX,cctvY), arrow: 2, info, &m)
cctvWorking(index+1, info, map: m, &ans)
onCctv((cctvX,cctvY), arrow: 0, info, &m2)
onCctv((cctvX,cctvY), arrow: 1, info, &m2)
onCctv((cctvX,cctvY), arrow: 3, info, &m2)
cctvWorking(index+1, info, map: m2, &ans)
onCctv((cctvX,cctvY), arrow: 0, info, &m3)
onCctv((cctvX,cctvY), arrow: 2, info, &m3)
onCctv((cctvX,cctvY), arrow: 3, info, &m3)
cctvWorking(index+1, info, map: m3, &ans)
onCctv((cctvX,cctvY), arrow: 1, info, &m4)
onCctv((cctvX,cctvY), arrow: 2, info, &m4)
onCctv((cctvX,cctvY), arrow: 3, info, &m4)
cctvWorking(index+1, info, map: m4, &ans)
break;
case 5:
onCctv((cctvX,cctvY), arrow: 0, info,&m)
onCctv((cctvX,cctvY), arrow: 1, info,&m)
onCctv((cctvX,cctvY), arrow: 2, info,&m)
onCctv((cctvX,cctvY), arrow: 3, info,&m)
cctvWorking(index+1, info, map: m, &ans)
break;
default:
break;
}
}
func BOJ_15683()
{
var info = mapInfo()
var index = 0
var ans = 9999999
print(ans == 9999999 ? 0 : ans)
}
BOJ_15683()
visit my github
