Baek_13460

원성혁·2023년 3월 7일
0

algorithm

목록 보기
21/21
post-thumbnail

오랜만에 수준이 높은 구현 문제를 풀어봤다.
사실 겉으로는 골드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함수를 활용해 작동한다.

구현을 더 연습하면서 삼성 코테를 확실하게 성공하겠다.

profile
AI개발자를 향해 전진중

0개의 댓글