[BOJ] 15683 - 감시

이준기·2022년 7월 24일
"삼성SW"boj
0

문제 링크

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

문제 설명

사진이 많으니 위 링크 참조 !

입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.

1차 시도

import copy

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cctv = [
  [-1],
  [[0], [1], [2], [3]],
  [[0,2], [1,3]],
  [[0,1], [1,2], [2,3], [3,0]],
  [[0,1,2], [1,2,3], [2,3,0]],
  [[0,1,2,3]]
]

graph = []
cctvPoint = []
ans = 100
n, m = map(int, input().split())

for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 and graph[i][j] != 6:
      cctvPoint.append((i, j, graph[i][j]))

def DFS(dir, nowGraph, nowY, nowX):
  nx = dx[dir] + nowX
  ny = dy[dir] + nowY

  if nx >= 0 and ny >= 0 and nx < m and ny < n:
    if nowGraph[ny][nx] == 0:
      nowGraph[ny][nx] = '#'
      DFS(dir, nowGraph, ny, nx)
    elif nowGraph[ny][nx] != '#' and nowGraph[ny][nx] != 6:
      DFS(dir, nowGraph, ny, nx)

def sol(cctvLeft, nowGraph):
  global ans
  if not cctvLeft:

    for i in range(n):
      print(nowGraph[i])

    sum = 0
    for i in range(n):
      for j in range(m):
        if nowGraph[i][j] == 0:
          sum += 1
    ans = min(ans, sum)
    print(sum)
  else:
    cctvNowY, cctvNowX, cctvNowNum = cctvLeft.pop()
    for dirs in cctv[cctvNowNum]:
      nextGraph = copy.deepcopy(nowGraph)  # 그래프 유지 주의!
      for dir in dirs:
        DFS(dir, nextGraph, cctvNowY, cctvNowX)
        sol(cctvLeft, nextGraph)

sol(cctvPoint, graph)

print(ans)
6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
[1, '#', '#', '#', '#', '#']
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
15
[1, 0, 0, 0, 0, 0]
['#', 1, '#', '#', '#', '#']
['#', 0, 1, '#', '#', '#']
['#', 0, 0, 1, '#', '#']
['#', 0, 0, 0, 1, '#']
['#', 0, 0, 0, 0, 1]
15
[1, 0, 0, 0, 0, 0]
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, '#', 1, '#', '#', '#']
[0, '#', 0, 1, '#', '#']
[0, '#', 0, 0, 1, '#']
[0, '#', 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
['#', 1, 0, 0, 0, 0]
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
23
[1, '#', 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
23
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, '#', 1, '#', '#']
[0, 0, '#', 0, 1, '#']
[0, 0, '#', 0, 0, 1]
24
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
['#', '#', 1, 0, 0, 0]
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
[1, 0, '#', 0, 0, 0]
[0, 1, '#', 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, '#', 1, '#']
[0, 0, 0, '#', 0, 1]
27
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
['#', '#', '#', 1, 0, 0]
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, '#', 0, 0]
[0, 1, 0, '#', 0, 0]
[0, 0, 1, '#', 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, '#', 1]
29
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
['#', '#', '#', '#', 1, 0]
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, '#', 0]
[0, 1, 0, 0, '#', 0]
[0, 0, 1, 0, '#', 0]
[0, 0, 0, 1, '#', 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
30
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
['#', '#', '#', '#', '#', 1]
25
[1, 0, 0, 0, 0, '#']
[0, 1, 0, 0, 0, '#']
[0, 0, 1, 0, 0, '#']
[0, 0, 0, 1, 0, '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
15
  • 백트래킹에서 마지막 원소가 끝났을때, 다시 append를 안해줘서 위와 같은 오류가 났다.
  • 위 오류를 고치고 모든 예시가 통과했는데 틀렸댄다,, 이럴때는 특수 케이스는 다 맞은것 같으니, 편안한 마음으로 문제와 코드를 유심히 보자.. 자세히 보니 cctv4번에서 [3,0,1]을 추가안했었다!

맞은 코드

import copy
import sys

#sys.setrecursionlimit(10**9)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cctv = [
  [-1],
  [[0], [1], [2], [3]],
  [[0,2], [1,3]],
  [[0,1], [1,2], [2,3], [3,0]],
  [[0,1,2], [1,2,3], [2,3,0], [3,0,1]],
  [[0,1,2,3]]
]

graph = []
cctvPoint = []
ans = 100
n, m = map(int, input().split())

for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 and graph[i][j] != 6:
      cctvPoint.append((i, j, graph[i][j]))

def DFS(dir, nowGraph, nowY, nowX):
  nx = dx[dir] + nowX
  ny = dy[dir] + nowY

  if nx >= 0 and ny >= 0 and nx < m and ny < n:
    if nowGraph[ny][nx] == 0:
      nowGraph[ny][nx] = '#'
      DFS(dir, nowGraph, ny, nx)
    elif nowGraph[ny][nx] != 6:
      DFS(dir, nowGraph, ny, nx)

def sol(cctvLeft, nowGraph):
  global ans
  if not cctvLeft:
    '''
    for i in range(n):
      print(nowGraph[i])
    '''
    sum = 0
    for i in range(n):
      for j in range(m):
        if nowGraph[i][j] == 0:
          sum += 1
    ans = min(ans, sum)
    #print(sum)
  else:
    cctvNowY, cctvNowX, cctvNowNum = cctvLeft.pop()
    for dirs in cctv[cctvNowNum]:
      #print(dirs)
      nextGraph = copy.deepcopy(nowGraph)  # 그래프 유지 주의
      for dir in dirs:
        DFS(dir, nextGraph, cctvNowY, cctvNowX)
      sol(cctvLeft, nextGraph)
    cctvLeft.append((cctvNowY, cctvNowX, cctvNowNum))

sol(cctvPoint, graph)

print(ans)
profile
이준기
Hongik CE
이전 포스트

[BOJ] 14891 - 톱니바퀴

다음 포스트

[CS] HTTP와 HTTPS

0개의 댓글