파이썬으로 풀어보는 백준 15683번: 감시 (삼성 A형 기출 문제)

Python/문제풀이 (삼성 A형 대비)

by 코딩하는 낙타 2020. 2. 10. 18:03

https://www.acmicpc.net/problem/15683

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

내 풀이:

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

def camera(lst, arr):
    global result, M
    for idx, dir in enumerate(lst):
        if arr[cctv[idx][0]][cctv[idx][1]] == 1:
            y = cctv[idx][0]
            x = cctv[idx][1]
            ny = y + dy[dir]
            nx = x + dx[dir]
            while 0 <= ny <= N-1 and 0 <= nx <= M-1 and arr[ny][nx] != 6:
                if arr[ny][nx] == 0:
                    arr[ny][nx] = 7
                ny += dy[dir]
                nx += dx[dir]
 
        elif arr[cctv[idx][0]][cctv[idx][1]] == 2:
            y = cctv[idx][0]
            x = cctv[idx][1]
            ny1 = y + dy[dir]
            nx1 = x + dx[dir]
            ny2 = y + dy[(dir+2)%4]
            nx2 = x + dx[(dir+2)%4]
            while 0 <= ny1 <= N-1 and 0 <= nx1 <= M-1 and arr[ny1][nx1] != 6:
                if arr[ny1][nx1] == 0:
                    arr[ny1][nx1] = 7
                ny1 += dy[dir]
                nx1 += dx[dir]
 
            while 0 <= ny2 <= N-1 and 0 <= nx2 <= M-1 and arr[ny2][nx2] != 6:
                if arr[ny2][nx2] == 0:
                    arr[ny2][nx2] = 7
                ny2 += dy[(dir+2)%4]
                nx2 += dx[(dir+2)%4]
 
        elif arr[cctv[idx][0]][cctv[idx][1]] == 3:
            y = cctv[idx][0]
            x = cctv[idx][1]
            ny1 = y + dy[dir]
            nx1 = x + dx[dir]
            ny2 = y + dy[(dir + 1) % 4]
            nx2 = x + dx[(dir + 1) % 4]
            while 0 <= ny1 <= N-1 and 0 <= nx1 <= M-1 and arr[ny1][nx1] != 6:
                if arr[ny1][nx1] == 0:
                    arr[ny1][nx1] = 7
                ny1 += dy[dir]
                nx1 += dx[dir]
 
            while 0 <= ny2 <= N-1 and 0 <= nx2 <= M-1 and arr[ny2][nx2] != 6:
                if arr[ny2][nx2] == 0:
                    arr[ny2][nx2] = 7
                ny2 += dy[(dir + 1) % 4]
                nx2 += dx[(dir + 1) % 4]
 
        elif arr[cctv[idx][0]][cctv[idx][1]] == 4:
            y = cctv[idx][0]
            x = cctv[idx][1]
            ny1 = y + dy[dir]
            nx1 = x + dx[dir]
            ny2 = y + dy[(dir + 1) % 4]
            nx2 = x + dx[(dir + 1) % 4]
            ny3 = y + dy[(dir + 2) % 4]
            nx3 = x + dx[(dir + 2) % 4]
 
            while 0 <= ny1 <= N-1 and 0 <= nx1 <= M-1 and arr[ny1][nx1] != 6:
                if arr[ny1][nx1] == 0:
                    arr[ny1][nx1] = 7
                ny1 += dy[dir]
                nx1 += dx[dir]
 
            while 0 <= ny2 <= N-1 and 0 <= nx2 <= M-1 and arr[ny2][nx2] != 6:
                if arr[ny2][nx2] == 0:
                    arr[ny2][nx2] = 7
                ny2 += dy[(dir + 1) % 4]
                nx2 += dx[(dir + 1) % 4]
 
            while 0 <= ny3 <= N-1 and 0 <= nx3 <= M-1 and arr[ny3][nx3] != 6:
                if arr[ny3][nx3] == 0:
                    arr[ny3][nx3] = 7
                ny3 += dy[(dir + 2) % 4]
                nx3 += dx[(dir + 2) % 4]
 
        elif arr[cctv[idx][0]][cctv[idx][1]] == 5:
            y = cctv[idx][0]
            x = cctv[idx][1]
            ny1 = y + dy[dir]
            nx1 = x + dx[dir]
            ny2 = y + dy[(dir + 1) % 4]
            nx2 = x + dx[(dir + 1) % 4]
            ny3 = y + dy[(dir + 2) % 4]
            nx3 = x + dx[(dir + 2) % 4]
            ny4 = y + dy[(dir + 3) % 4]
            nx4 = x + dx[(dir + 3) % 4]
 
            while 0 <= ny1 <= N-1 and 0 <= nx1 <= M-1 and arr[ny1][nx1] != 6:
                if arr[ny1][nx1] == 0:
                    arr[ny1][nx1] = 7
                ny1 += dy[dir]
                nx1 += dx[dir]
 
            while 0 <= ny2 <= N-1 and 0 <= nx2 <= M-1 and arr[ny2][nx2] != 6:
                if arr[ny2][nx2] == 0:
                    arr[ny2][nx2] = 7
                ny2 += dy[(dir + 1) % 4]
                nx2 += dx[(dir + 1) % 4]
 
            while 0 <= ny3 <= N-1 and 0 <= nx3 <= M-1 and arr[ny3][nx3] != 6:
                if arr[ny3][nx3] == 0:
                    arr[ny3][nx3] = 7
                ny3 += dy[(dir + 2) % 4]
                nx3 += dx[(dir + 2) % 4]
 
            while 0 <= ny4 <= N-1 and 0 <= nx4 <= M-1 and arr[ny4][nx4] != 6:
                if arr[ny4][nx4] == 0:
                    arr[ny4][nx4] = 7
                ny4 += dy[(dir + 3) % 4]
                nx4 += dx[(dir + 3) % 4]
 
    cnt = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0:
                cnt += 1
 
    if result > cnt:
        result = cnt
    return
 
 
def make(idx, lst):
    global n, N
    if idx == n:
        new_arr = [i[:] for i in arr_init]
        camera(lst, new_arr)
 
        return
 
    for num in range(4):
        lst.append(num)
        make(idx+1, lst)
        lst.pop(-1)
 
 
N, M = map(int,input().split())
arr_init = [list(map(int,input().split())) for _ in range(N)]
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
dir = [0, 1, 2, 3]
result = N * M
 
cctv = []
for i in range(N):
    for j in range(M):
        if arr_init[i][j] not in [0, 6]:
            cctv.append([i, j, arr_init[i][j]])
 
n = len(cctv)
 
make(0, [])
 
print(result)

 

Python3, 2944ms

카메라 종류가 5개나 되다 보니 각 카메라에 대해서 함수를 정의해 해결하지 못하고 각각의 경우에 필요한 만큼 while문을 만들어 문제를 해결했다.

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

def go(idx, now):
    global N, M, ans
    if idx == len(cctv):
        res = 0
        for i in range(N):
            for j in range(M):
                if now[i][j] == 0:
                    res += 1
        ans = min(ans, res)
        return
 
    y, x, k = cctv[idx]
    if k == 1:
        for dir in range(4):
            new = [now[i][:] for i in range(N)]
            show(new, y, x, dir)
            go(idx+1, new)
 
    elif k == 2:
        for dir in range(2):
            new = [now[i][:] for i in range(N)]
            show(new, y, x, dir)
            show(new, y, x, dir+2)
            go(idx+1, new)
 
    elif k == 3:
        for dir in range(4):
            new = [now[i][:] for i in range(N)]
            show(new, y, x, dir)
            show(new, y, x, (dir+1)%4)
            go(idx + 1, new)
 
    elif k == 4:
        for dir in range(4):
            new = [now[i][:] for i in range(N)]
            show(new, y, x, dir)
            show(new, y, x, (dir+1) % 4)
            show(new, y, x, (dir+2) % 4)
            go(idx + 1, new)
 
    elif k == 5:
        new = [now[i][:] for i in range(N)]
        show(new, y, x, 0)
        show(new, y, x, 1)
        show(new, y, x, 2)
        show(new, y, x, 3)
        go(idx + 1, new)
 
 
def show(new, y, x, dir):
    global N, M
    ny = y + dy[dir]
    nx = x + dx[dir]
    while 0 <= ny <= N-1 and 0 <= nx <= M-1 and new[ny][nx] != 6:
        if new[ny][nx] == 0:
            new[ny][nx] = 9
        ny += dy[dir]
        nx += dx[dir]
    return
 
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
cctv = []
for i in range(N):
    for j in range(M):
        if arr[i][j] not in (0, 6):
            cctv.append((i, j, arr[i][j]))
 
ans = 64
go(0, arr)
print(ans)

 

Python3, 844ms

cctv가 한 방향에 대해 찍는 것을 show라는 함수를 만들어 처리함으로써 코드 길이를 많이 줄일 수 있었다.

저작자표시

'Python > 문제풀이 (삼성 A형 대비)' 카테고리의 다른 글

파이썬으로 풀어보는 백준 17142번: 연구소 3 (삼성 A형 기출 문제) (0)	2020.02.11
파이썬으로 풀어보는 백준 12100번: 2048 (삼성 A형 기출 문제) (0)	2020.02.11
파이썬으로 풀어보는 백준 16234번: 인구 이동 (삼성 A형 기출 문제) (0)	2020.02.08
파이썬으로 풀어보는 백준 15686번 치킨 배달 (삼성 A형 기출 문제) (0)	2020.02.08
파이썬으로 풀어보는 백준 17779번: 게리맨더링 2 (삼성 A형 기출 문제) (0)	2020.02.07