[Python] 13460번. 구슬 탈출 2

문제 링크

성능 요약

메모리: 35176 KB, 시간: 60 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색

 

from collections import deque

dir=((-1,0),(1,0),(0,-1),(0,1))

#1.입력
N,M=map(int,input().split())
matrix=[list(input()) for _ in range(N)]

#2.자료형 정의
#빨간,파란 구슬 각각의 위치를 생각해야하므로 visited는 4차원이여야함
visited=[[[[False]*M for _ in range(N)]
          for _ in range(M)]
          for _ in range(N)]
#빨간구슬,파란구슬 위치 저장
for y in range(N):
    for x in range(M):
        if matrix[y][x]=='R':
            ry,rx=y,x
        if matrix[y][x]=='B':
            by,bx=y,x
matrix[ry][rx]='.' #위치 저장했으니 이동할 수 있게 수정
matrix[by][bx]='.'

#3.동작 알고리즘
def move(y,x,dy,dx):
    dist=0 #움직인 거리
    while True:
        ny=y+dy
        nx=x+dx

        if matrix[ny][nx]=='#': #벽이라면
            break

        y=ny
        x=nx
        dist+=1

        if matrix[y][x]=='O': #구멍이라면
            break

    return y,x,dist,matrix[y][x]=='O' #구멍에 빠지면 True

def bfs(ry,rx,by,bx):
    queue=deque()
    queue.append((ry,rx,by,bx,0)) 
    visited[ry][rx][by][bx]=True

    while queue:
        ry,rx,by,bx,cnt=queue.popleft()

        #10번이 넘으면
        if cnt>=10:
            continue
        
        for dy,dx in dir:
            nry,nrx,rdist,rhole=move(ry,rx,dy,dx)
            nby,nbx,bdist,bhole=move(by,bx,dy,dx)

            if bhole: #파란공이 구멍에 빠지면
                continue

            if rhole: #빨간공이 구멍에 빠지면
                return cnt+1

            #만약 두 공이 같은 위치라면
            if nry==nby and nrx==nbx:
                if rdist>bdist: #더 먼거리가 더 뒤에서 시작함
                    nry-=dy
                    nrx-=dx
                else:
                    nby-=dy
                    nbx-=dx
            
            if not visited[nry][nrx][nby][nbx]:
                visited[nry][nrx][nby][nbx]=True
                queue.append((nry,nrx,nby,nbx,cnt+1))

    return -1 

ans=bfs(ry,rx,by,bx)

#4.출력
print(ans)

 

 

문제를 잘못 이해해서 결국,,, 지피티와 함께 풀었다,,,

틀렸던 이유!!

>> 한 번 기울여지면 구슬이 쭉 간다! 

>> 같은 위치에 도착하면 먼저 온 구슬이 차지한다!

 

 

이제는 뭔가 문제를 읽으면 아예 못 풀지는 않고 어려운 문제라도 60% 정도는 푼다고 생각했는데 이번 문제를 풀고 얼마나 오만했는지 또 깨달았다. 이 문제조차 못 푸는데 삼성 코테는 어떻게 뚫고, 현대오토에버 코테는 어떻게 뚫을까,,,

작년에 코테에서 골드 정도는 가볍게 풀 정도의 실력을 만들었어야했는데 내가 너무 안일하게 지낸 1년이였다는걸 느꼈다.

상반기 시작까지 3개월 남짓 남았는데 매일 문제를 풀며 지금이라도 후회하지 않도록 열심히 해야겠다.