boj 14502 연구소 (골드5)

boj 14502 연구소

이것도 삼성기출이다!
bfs 기반인것 같긴한데 벽을 3군데를 골라서 세워야 하므로 추가적인 처리를 조금더 해줘야한다.
주어진 맵에서 0인곳중에 3군데를 골라 벽을 추가로 세울수 있는데 어디에 세우는게 최선일지를 살짝 고민해보다가 이건 그냥 모든 경우의수를 다 세워봐야 할것같다고 결론내렸다.

주어진 맵의 최대크기가 8*8 이므로 완전탐색으로 다 해봐도 괜찮을것같다.

대략적으로 계산해보면 64C3 = 약 4만정도 이고, bfs로 주어진 상황에서 맵을 다 탐색하려면 많아도 8*8 이기에 많아도 64번 이내로 소요될테니 대략 60 으로 잡고, 몇군데 살아있는지 체크하려고 한번 다 보면 또 대략 60번정도
4만 * 60 * 60 = 대략 1억얼마?

파이썬은 느리니깐 1초에 2천만쯤으로 잡고 보면 안될라나 싶기도하다

일단 생각나는 방법이 없어서 이렇게 짜봤다

list(itertools.permutation(arr,n))
배열에서 n개짜리 조합을 짜서 list로 만드는 방법이다!
import itertools 하고 쓰면 된다.
itertools 에 있는 순열, 조합 함수들은 몇번 써봤지만 정말 가끔써서 그런지 손에 익지는 않는다. 검색 막히면 못쓸듯..
혹시 기억안나면 그냥 n중포문 돌려서 직접 함수 만들어야 할 것 같다.

import itertools
import copy
from collections import deque

n,m = map(int,input().split())
dy = [0,1,0,-1]
dx = [1,0,-1,0]
answer_list = []

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

arr = []

for i in range(n):
  for j in range(m):
    if first_state[i][j] == 0:
      arr.append((i,j))

wall_list = list(itertools.permutations(arr,3))

def collision(state):
  global n,m
  state = state
  queue = deque()
  for i in range(n):
    for j in range(m):
      if state[i][j] == 2 :
        queue.append((i,j))
        while(queue):
          y,x = queue.popleft()
          for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]

            if ny <0 or nx < 0 or ny >=n or nx >=m:
              continue

            if state[ny][nx] == 0:
              state[ny][nx] = 2
              queue.append((ny,nx))

  return state

def safecheck(state):
  global n,m
  count = 0
  for i in range(n):
    for j in range(m):
      if state[i][j] == 0:
        count += 1

  return count

for wall in wall_list:
  # state = first_state
  state = copy.deepcopy(first_state)
  state[wall[0][0]][wall[0][1]] = 1
  state[wall[1][0]][wall[1][1]] = 1
  state[wall[2][0]][wall[2][1]] = 1
  state = collision(state)
  answer_list.append(safecheck(state))


print(max(answer_list))
   

회고

다 짜고 돌렸는데 결과가 계속 0이나와서 print로 단계별로 찍어보며 틀린부분 찾아봤다
문제는 바로 배열의 복사
맽 밑에쪽에 주석처리해둔 state = first_state 요부분이 문제였다.

파이썬은 그냥 요렇게 복사하면 call by reference로 주소값째로 복사되어 state 건드리면 first_state도 같이변해버린다.

주소가 아니라 값만 복사하려면 deelcopy 라는걸 써야한다.
import copy 해주고
b = copy.deepcopy(a)

요렇게 처리하면 원하는대로 일반적인 값 복사가 가능하다.

이번학기에 컴퓨터비전 팀플 코드짜다가도 이거때메 잘못된부분 찾느라 한참 시간썼었는데 오랜만에 보니 여전히 생각도 못하고있었다.

c++쓰던 버릇이 있어서 파이썬은 배열복사가 reference째로 넘겨진다는걸 자꾸 놓친다.
꼭 기억해놔야겠다

결과

파이썬으로 돌리면 시간초과난다 ㅠㅠ
그래도 삼성 코테는 채점서버가 PyPy3 환경에서 돌아간다 하니 맞긴 했을것같다.

파이썬으로 돌려도 통과할수 있는 더 빠른 방법에 대해서 연구해봐야겠다

끝!