2022. 11. 8. 22:19ㆍ공부/알고리즘
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
SSAFY 코딩테스트까지 앞으로 2주 남은 이 시점에 알고리즘력 강화에 좀더 집중해보자
백트래킹
위 문제는 각 cctv의 방향이 여러개인 것이 포인트이며, 이로 발생하는 사각지대의 개수를 구해야 한다.
CCTV는 여러개가 존재하며, 모든 방법을 확인해야하므로 백트래킹 문제임을 떠올렸다.
그러나 이 문제는 구현에서 정말 어려움을 겪었다.
보통 백트래킹은 변수 하나를 넣고 빼고 하는 식으로 했었는데 이건 배열을 이리저리 돌려가면서 값을 넣어보고 빼고 해야했다.
왜냐하면 여러 cctv가 같은 곳을 보면 중복이 발생하기 때문
먼저 어떤식으로 구현할 지 생각했는데 cctv의 좌표들을 담은 배열을 만들고
백트래킹으로 배열의 크기만큼 도달하면 빈칸을 세는 방식으로 생각했다.
이후 cctv가 한 방향을 볼 때 막히는 곳 까지 값을 집어넣어주는 hashfilling() 함수와
hashfilling()함수로 넣어주었던 값을 다시 0으로 바꿔주는 zerofilling() 함수를 구현했는데
여기서 한가지 주의할 점은, 구조만 같게하고 "#"와 0의 자리만 바꿔준다면 전 단계에서 넣어준 값도 0으로 바뀌기 때문에
반드시 이번에 넣어준 값만 다시 0으로 바꿔줄 필요가 있었다.
따라서 바꿔준 좌표들을 저장할 큐 buff를 만들고 각 단계마다 몇번 buff에 넣어줬는지를 세는 count 변수를 만들었다.
그렇게 0을 #으로 바꿔주는 함수와 다시 원래대로 돌려주는 함수를 만들고 나니
기존 백트래킹처럼 구현할 수 있었다.
|
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
|
from collections import deque
def hashfilling(x,y, dir, zeroes, k):
dxy = ((0,1),(1,0),(0,-1),(-1,0))
nx, ny = x+dxy[dir][0], y+dxy[dir][1]
while 0<=nx<n and 0<=ny<m and src[nx][ny] != 6:
if src[nx][ny] == 0:
src[nx][ny] = 8
zeroes -= 1
buff.append([nx,ny])
count[k] += 1
nx, ny = nx+dxy[dir][0], ny+dxy[dir][1]
return zeroes
def zerofilling(x,y,zeroes, k):
while count[k]:
x, y = buff.pop()
src[x][y] = 0
zeroes += 1
count[k] -= 1
return zeroes
def backtracking(k):
global n, m, zeroes
if k == len(cctv):
return res.append(zeroes)
for i in range(4):
x, y = cctv[k]
cctvType = src[x][y]
if cctvType == 1:
zeroes = hashfilling(x, y, i, zeroes, k)
backtracking(k+1)
zeroes = zerofilling(x, y, zeroes, k)
elif cctvType == 2 and i < 2:
dirs = ((0,2),(1,3))
for j in dirs[i]:
zeroes = hashfilling(x, y, j, zeroes, k)
backtracking(k+1)
zeroes = zerofilling(x, y, zeroes, k)
elif cctvType == 3:
dirs = ((0,1),(1,2),(2,3),(3,0))
for j in dirs[i]:
zeroes = hashfilling(x, y, j, zeroes, k)
backtracking(k+1)
zeroes = zerofilling(x, y, zeroes, k)
elif cctvType == 4:
dirs = ((0,1,2),(1,2,3),(2,3,0),(3,0,1))
for j in dirs[i]:
zeroes = hashfilling(x, y, j, zeroes, k)
backtracking(k+1)
zeroes = zerofilling(x, y, zeroes, k)
elif cctvType == 5 and i < 1:
dirs = ((0,1,2,3),)
for j in dirs[i]:
zeroes = hashfilling(x, y, j, zeroes, k)
backtracking(k+1)
zeroes = zerofilling(x, y, zeroes, k)
global n, m, zeroes
n, m = map(int, input().split())
src = [ list(map(int, input().split())) for _ in range(n) ]
cctv = []
res = []
zeroes = 0
buff = deque()
for x in range(n):
for y in range(m):
if 1 <= src[x][y] <= 5:
cctv.append((x,y))
if src[x][y] == 0:
zeroes += 1
count = [0]*len(cctv)
backtracking(0)
print(min(res))
|
cs |
그런데 이 문제와 같이 모든 개체가 똑같이 n번 확인해야하는 문제라면 n진법을 사용해도 된다.
n진법
|
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
|
from copy import deepcopy
def hashFilling(x, y, dir, n, m):
dxy = [[0,1],[1,0],[0,-1],[-1,0]]
nx, ny = x+dxy[dir][0], y+dxy[dir][1]
while 0<=nx<n and 0<=ny<m and src[nx][ny] != 6:
if src[nx][ny] == 0:
src[nx][ny] = 7
nx, ny = nx+dxy[dir][0], ny+dxy[dir][1]
n, m = map(int, input().split())
origin = [list(map(int, input().split())) for _ in range(n)]
src = deepcopy(origin)
cctvs = []
res = -1
for x in range(n):
for y in range(m):
if 1<= src[x][y] < 6:
cctvs.append([x,y])
tries = 4**len(cctvs)
ways = [0]*len(cctvs)
for t in range(tries):
for i in range(len(cctvs)-1, -1, -1):
ways[i] = t % 4
t = t // 4
for cctv in range(len(cctvs)):
x, y = cctvs[cctv]
model = src[x][y]
if model == 1:
hashFilling(x, y, ways[cctv], n, m)
elif model == 2:
directions = [[0,2],[1,3]]
for direction in directions[ways[cctv] % 2]:
hashFilling(x,y, direction, n, m)
elif model == 3:
directions = [[0,1],[1,2],[2,3],[3,0]]
for direction in directions[ways[cctv]]:
hashFilling(x,y, direction, n, m)
elif model == 4:
directions = [[0,1,2],[1,2,3],[2,3,0],[3,0,1]]
for direction in directions[ways[cctv]]:
hashFilling(x,y, direction, n, m)
elif model == 5:
directions = [[0,1,2,3]]
for direction in directions[ways[cctv] %1]:
hashFilling(x,y, direction, n, m)
count = 0
for x in range(n):
for y in range(m):
if src[x][y] == 0:
count += 1
if res == -1 or res > count:
res = count
src = deepcopy(origin)
print(res)
|
cs |
그런데 이 방법은 deepcopy를 사용해서 그런지 시간이 백트래킹에 비해 더 많이 걸린다.
초기화 하는 과정을 좀 더 손보면 쓸만한 방법인 것 같다.
972ms가 n진법, 460ms가 백트래킹이다.
'공부 > 알고리즘' 카테고리의 다른 글
| 코딩테스트에 필요한 파이썬 문법 정리 (0) | 2022.11.10 |
|---|---|
| BOJ 18808. 스티커 붙이기 (0) | 2022.11.09 |
| [SWEA] 회문 (0) | 2022.11.03 |
| [SWEA] 암호문 3 (0) | 2022.11.01 |
| [SWEA] 최대 상금 문제 풀이 (0) | 2022.10.30 |