[BOJ / 파이썬] 15683 감시

https://soohyun6879.tistory.com/241

[백준/Python] 감시

: 아.. 그래도 꽤 접근했는데, 끝내 정답은 못 맞추네.

:

 그리고 제 생각에 이 문제는 정말 짜기 까다롭습니다. 대충 어떤 느낌이냐면 대충 구현 방향은 잡았고 천천히 구현을 하려고 하는데 짜다보니 꼬이고 코드 길이가 끝없이 길어지고, 기껏 완성한 후에 돌렸더니 결과가 이상해서 코드 중간중간에 끊임없이 출력문을 넣어서 잘못된 부분은 간신히 찾아냈지만 코드를 어떻게 고쳐야할지는 모르는 상황인겁니다. 시간을 엄청 쏟았지만 결국 해결하지 못해 다른 사람의 코드를 찾아보니 신기하긴 한데 내가 직접 다시 짜려고 한다면 자신은 없어서 막막한 그런 느낌을 이전에 혼자 공부하면서 받아본 분이라면 공감할 것입니다. 힘들더라도 역시 답은 노오오오력밖에 없으니 힘내서 계속 가보겠습니다.

진짜 이 사람 말 그대로의 과정을 거친 문제다.

답은 노오오력밖에 없단다.. 힘내보자.. 다시 돌아와서 풀기... 흑흐그ㅡ흐긓 잘 하고 싶다고!!

 

(22.07.28)

---

다시 풀어봤다.

확실히 진도는 잘 나가고, 전체적인 구조도 잡힌다.

실력이 늘기는 늘었다. 

물론 충분하지 않다. 

왜냐하면 못 풀었으니까. 

1시간 걸린 내용을 일단 기록한다.  

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
directionDict = {
  'top': 0,
  'right':1,
  'down':2,
  'left':3  
}
rotateDict = {
  1:[['right'], ['down'], ['left'], ['top'] ],
  2:[['left','right'],['top','down']],
  3:[['top','right'],['right','down'],['down','left'],['left','down']],
  4:[['left','top','right'],['top','right','down'],['right','down','left'],['top','left','down']],
  5:[['left','top','right','down']]
}
# cctv 정보 저장: [cctv종류, 위치x, 위치y] 
cctv = []
for x in range(n):
  for y in range(m):
    if office[x][y] != 0 and office[x][y] != 6:
      cctv.append([office[x][y], x, y])
cctvNum = len(cctv)


# directionDict의 key값 들어옴. x, y부터 시작해서 그 key값 방향으로 가능할 때까지 칠해주기
def checkView(direction, x, y):
  i = directionDict[direction]
  nx = x + dx[i]
  ny = y + dy[i]
  while 0 <= nx < n and 0 <= ny < m and office[nx][ny] != 6:
    office[nx][ny] = '#'
    nx += dx[i]
    ny += dy[i]
  return

def getCountBlindSpotNow():
  cnt = 0
  for x in range(n):
    for y in range(m):
      if office[x][y] == '0':
        cnt += 1
  return cnt

minBlindSpot = n*m

def cctvCheck(i):
  global minBlindSpot
  
  if i == cctvNum-1:
    
    for rotateDirection in rotateDict[cctv[i][0]]:
      # 첫 번째라면 'left', 'right' 돌기. 그 cctv시작위치도 같이 주기
      for direction in rotateDirection:
        checkView(direction, cctv[i][1], cctv[i][2])
        for k in range(n):
          print(office[k])
        print("")
        minBlindSpot = min(minBlindSpot, getCountBlindSpotNow())
        ## checkView 한거 원래대로 지우기 ##
    return    
  # 2라면 [['left','right'],['top','down']] 배열 도는거
  for rotateDirection in rotateDict[cctv[i][0]]:
    # 첫 번째라면 'left', 'right' 돌기. 그 cctv시작위치도 같이 주기
    
    for direction in rotateDirection:
      checkView(direction, cctv[i][1], cctv[i][2])
      for k in range(n):
        print(office[k])
      print("")
  
  cctvCheck(i+1)
      
  return 

cctvCheck(0)
print(minBlindSpot)

실행결과 콘솔로 찍은 것.

😥뭘 못 해냈냐면,

- DFS 구현. 엄밀히 말하자면 백트래킹

 

    : 한 번 들어갔다가 뒤로 돌아와야하는데 그게 안 된다. 나올 때 보드를 다시 클리어해줘야 하는데, 미리 보드를 복사하는 수 밖에 없는건지.. 

    : 백트래킹의 흐름을 아직 덜 이해한 것 같다.

 

 

😌전보다 나아진 것은,

    : 시뮬레이션적인 구현사항, 예를 들어 방향성에 대해 케이스를 나누고 기능별로 함수를 나눠준다던가의 작업에 익숙해진 것 같다. 

    : 코드 인내력, 자신감, 코드가 길어지면 정신 못 차리고 내 코드 내가 못 읽던것과 다르게 구조화가 되는 듯 하다. 그리고 코드가 길어졌을 때 스스로를 의심하면서 문제에 쫄지는 않는다. 

    : 각 함수의 정확성, 각 함수들이 자기가 할 일을 해낸다. 내가 아 이건 못 짜겠는데라고 판단한 위의 백트래킹 부분을 제외하면 의도한 로직대로 작동한다.

 

🙄 실수도 중간중간 있어서 테케 넣어가며 돌렸을 때 오류를 좀 잡아냈다. 자료구조의 타입을 순간순간 헷갈려서 dictionary한테 key값을 함수한테 인자 주듯이 해서 오류가 났었다.

 

비록 틀렸지만 오늘은 일단 이 정도 발전에 마무리하고 다른 분들 코드 좀 찾아봐서 정리해봐야겠다. 다른 새로운 문제들 더 풀어보는 게 중요할 것 같기 때문이다.

 

내가 헷갈리는 파트를 다른 분이 구현한 것 메모

 

(22.08.06)

---

import sys
input = sys.stdin.readline
import copy

n, m = map(int, input().split())
cctv = []
board = []
watch = [
  [],
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [0, 3]],
  [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
  [[0, 1, 2, 3]]
]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
  row = list(map(int, input().split()))
  for j in range(m):
    if row[j] in [1, 2, 3, 4, 5]:
      cctv.append((row[j], i, j))
  board.append(row)

def fill(board_temp, directions, x, y):
  for d in directions:
    nx = x
    ny = y
    while True:
      nx += dx[d]
      ny += dy[d]
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        break
      if board_temp[nx][ny] == 6:
        break
      elif board_temp[nx][ny] == 0:
        board_temp[nx][ny] = '#'
        
def dfs(depth, board):
  global result
  if depth == len(cctv):
    count = 0
    for i in range(n):
      count += board[i].count(0)
    result = min(result, count)
    return
  temp = copy.deepcopy(board)
  cctv_num, x, y = cctv[depth]
  for watch_direction in watch[cctv_num]:
    fill(temp, watch_direction, x, y)
    dfs(depth+1, temp)
    temp = copy.deepcopy(board)

result = int(1e9)
dfs(0, board)
print(result)

 

아.. 이제 백트래킹도 이해하고, 전에 cctv구현도 한 적이 있어서 풀 수 있을 줄 알았는데..

board를 따로 temp로 빼서 구현하는데서 놓쳐서 결과를 못 냈다.. ;; ㅠㅜㅠㅜㅠㅜㅜㅠㅜㅠ ㅠ

속상... 그래도 이제 코드 내용이 한 번에 이해가 간다.. 반복하자 시뮬 유형! ㅠㅜ

 

(22.10.09)