오랜만에 수준이 높은 구현 문제를 풀어봤다.
사실 겉으로는 골드1이지만 실제 난이도는 좀더 쉬웠고 어려운 점은 반례를 생각하는 점이었던 것 같다.
import sys
input = sys.stdin.readline
from collections import deque
N,M = map(int,input().split())
R_x,R_y,B_x,B_y,H_x,H_y = 0,0,0,0,0,0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
matrix = list()
for i in range(N):
temp = list(input().rstrip())
for t,v in enumerate(temp):
if v == 'R':
R_x,R_y = i,t
temp[t] = '.'
elif v == 'B':
B_x,B_y = i,t
temp[t] = '.'
elif v == 'O':
H_x,H_y = i,t
temp[t] = '.'
matrix.append(temp)
def move(R_x,R_y,B_x,B_y,n):
flag_R,flag_B = True,True
flag_FR,flag_FB = True,True
is_move = False
while flag_R or flag_B:
flag_R,flag_B = False,False
if flag_FR:
nrx,nry = R_x+dx[n],R_y+dy[n]
if 0<=nrx<N and 0<=nry<M and matrix[nrx][nry] == '.':
if nrx == B_x and nry == B_y:
if flag_FB == False:
R_x,R_y = nrx,nry
flag_R = True
is_move = True
if R_x == H_x and R_y == H_y:
flag_FR = False
else:
R_x,R_y = nrx,nry
flag_R = True
is_move = True
if R_x == H_x and R_y == H_y:
flag_FR = False
if flag_FB:
nbx,nby = B_x+dx[n],B_y+dy[n]
if 0<=nbx<N and 0<=nby<M and matrix[nbx][nby] == '.':
if nbx == R_x and nby == R_y:
if flag_FR == False:
B_x,B_y = nbx,nby
flag_B = True
is_move = True
if B_x == H_x and B_y == H_y:
flag_FB = False
else:
B_x,B_y = nbx,nby
flag_B = True
is_move = True
if B_x == H_x and B_y == H_y:
flag_FB = False
return R_x,R_y,B_x,B_y,is_move
answer = -1
def bfs(R_x,R_y,B_x,B_y):
global answer
dq = deque([(R_x,R_y,B_x,B_y,0)])
while dq:
rx,ry,bx,by,num = dq.popleft()
if num > 10:
break
elif rx == H_x and ry == H_y:
if not(bx == H_x and by == H_y):
if answer != -1:
answer = min(num,answer)
else:
answer = num
elif bx == H_x and by==H_y:
pass
else:
for i in range(4):
nrx,nry,nbx,nby,is_move = move(rx,ry,bx,by,i)
if is_move:
dq.append((nrx,nry,nbx,nby,num+1))
bfs(R_x,R_y,B_x,B_y)
print(answer)
두번 틀렸었는데 두 공이 겹치지 않음을 구현해야 했으며 빨간 공이 구멍에 빠진 후 파란공이 안빠져야지만 통과거나 파란공이 빠지면 실패 등의 규칙들을 추가해야했다.
또한 bfs방식에서 실패 한다고 끝이 아니라 총 횟수가 10번 전의 모든 상황을 살펴서 가장 최소 답안을 찾도록 코드를 고쳐서 결국 맞췄다.
move 함수가 핵심인데 빨강공과 파랑공을 한칸씩 움직인다. 나는 bool타입의 flag를 거의 5개를 썼는데 움직였는지, 구멍에 들어갔는지 를 flag로 체크한다.
bfs는 move함수를 활용해 작동한다.
구현을 더 연습하면서 삼성 코테를 확실하게 성공하겠다.