최초에는 deep copy를 사용했다.
BFS는 기본적으로 방문체크를 하고 방문했으면 continue를 해야 연산이 O(n)인데,
4개이상의 젤리가 만나는지 확인하려면 결국 방문처리로 확인해나가야한다.
방문처리로 값을 바꾸면서 나아가다가 4개 미만이면 원본을 유지해야 하기 때문에
deep copy를 사용함.
한번에 통과했으나 이번 경우에는 n이 적어서 그랬을 것으로 판단.
deepcopy를 한 만큼이 n이면 del하는 동안의 연산도 n. 즉 2n이라는 시간이 소요된다.
다른 사람의 코드 참고 후.
visit[][] 배열을 호출될때마다 초기화 >>> 이것도 n번 연산하지만 del필요가 없다. 실제로 연산이 1.5배 빨라짐
visit으로 BFS를 구현하는 tip 얻어감
cnt로 세어나가면서 4개이상일 경우만 원본을 바꾸고. 밑으로 내려주었다.
구현
import sys
from collections import deque
import copy
origin = []
for _ in range(12):
origin.append(list(map(str,sys.stdin.readline().strip())))
def BFS2(ll,a,b):
visit = [[0]*6 for __ in range(12)]
if ll[a][b]!='.':
q = deque()
q.appendleft((a,b))
stand = ll[a][b]
visit[a][b] = 1 #ㅂㅏ꾸지 말기
cnt = 1
while(q):
y,x = q.pop()
ny = [1,0,-1,0]
nx = [0,1,0,-1]
for o in range(4):
dy = y + ny[o]
dx = x + nx[o]
if (dy >= 12) or (dx >=6) or (dy < 0) or (dx <0):
continue
if (ll[dy][dx] == stand) and (visit[dy][dx] == 0):
q.appendleft((dy,dx))
visit[dy][dx] = 1
cnt+=1
if cnt>=4:
for u in range(12):
for p in range(6):
if visit[u][p]:
ll[u][p] = '.'
return ll
return False
def BFS(origin):
answer = False
for i in range(12): #72
for j in range(6):
temp = BFS2(origin,i,j)
if temp:
answer = True
origin = temp
for x in range(6):
chan = 11
for y in range(11,-1,-1):
if origin[y][x] != '.':
origin[chan][x] = origin[y][x]
if chan!=y:
origin[y][x] = '.'
chan-=1
if answer:
return origin
return answer
cnt = 0
temp = 1
while(temp):
temp = BFS(origin)
if temp:
origin = temp
cnt+=1
print(cnt)
스티커 붙히기 - 18808번과 유사한 개념. 조건을 충족할 때만 값을 바꾸어야 할 경우 >> 원본을 건드리지 않는 방법을 찾는다. visit
2048(EASY) - 12100번과 유사한 테크닉이 들어감. 한줄로 미루기.
42Seoul