코딩테스트/파이썬
백준 15683번 감시
도리닥
2021. 2. 6. 16:07
728x90
문제 설명
office는 사무실을 나타내는 배열, cctv는 사무실에 있는 cctv의 위치를 뜻한다. cctv가 없다는 뜻은 더이상 감시할 cctv가 없다는 뜻이므로 해당 사무실에서 0의 개수를 센 후 min_count와 비교해준다.
cctv가 존재하면 하나씩 pop을 하여 해당 cctv의 종류에 맞게 office의 배열을 설정한다. x_pos는 cctv의 행의 좌표, y_pos는 cctv의 열의 좌표다. 만약 cctv가 1번 cctv일 경우 감시할 방향의 경우의 수는 총 4개이므로 for문을 사용하여 감시할 영역을 '#'으로 바꾼다. 여기서 함수에서 인자로 받은 arr을 그대로 사용할 경우 배열 자체의 데이터가 바뀌기 때문에 copy_office로 복사한 후 copy_office의 값을 변경한다. 이렇게 총 5개의 cctv를 설정한다.
전체 코드
cctv = []
office = []
min_count = 65
M = 0
N = 0
def func(arr):
global office
global cctv
global M
global N
global min_count
if not cctv:
count = 0
for i in range(N):
for j in range(M):
if arr[i][j] == 0:
count += 1
min_count = min(min_count,count)
return
while cctv:
tmp = cctv.pop(0)
x_pos = tmp[0]
y_pos = tmp[1]
if arr[x_pos][y_pos] == 1:
for j in range(4):
copy_office = [item[:] for item in arr]
if j == 0:
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 1:
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
elif j == 2:
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 3:
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
func(copy_office)
cctv.insert(0, tmp)
elif arr[x_pos][y_pos] == 2:
for j in range(2):
copy_office = [item[:] for item in arr]
if j == 0:
for k in range(y_pos + 1, M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 1:
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
func(copy_office)
cctv.insert(0, tmp)
elif arr[x_pos][y_pos] == 3:
for j in range(4):
copy_office = [item[:] for item in arr]
if j == 0:
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
elif j == 1:
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 2:
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
elif j == 3:
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
func(copy_office)
cctv.insert(0, tmp)
elif arr[x_pos][y_pos] == 4:
for j in range(4):
copy_office = [item[:] for item in arr]
if j == 0:
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 1:
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
elif j == 2:
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
elif j == 3:
for k in range(y_pos+1,M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos+1,N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
func(copy_office)
cctv.insert(0, tmp)
elif arr[x_pos][y_pos] == 5:
copy_office = [item[:] for item in arr]
for k in range(y_pos + 1, M):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in reversed(range(x_pos)):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
for k in reversed(range(y_pos)):
if copy_office[x_pos][k] == 6:
break
if copy_office[x_pos][k] == 0:
copy_office[x_pos][k] = '#'
for k in range(x_pos + 1, N):
if copy_office[k][y_pos] == 6:
break
if copy_office[k][y_pos] == 0:
copy_office[k][y_pos] = '#'
func(copy_office)
cctv.insert(0, tmp)
return
return
def main():
global office
global M
global N
N, M = map(int,input().split())
for i in range(N):
office.append(list(map(int,input().split())))
for i in range(N):
for j in range(M):
if office[i][j] > 0 and office[i][j] < 6:
cctv.append([i,j])
func(office)
print(min_count)
return
if __name__ == "__main__":
main()728x90
반응형