[bfs/백준] 13460번 : 구슬 탈출2(어려운 문제)

- 문제 : https://www.acmicpc.net/problem/13460

 

Gold Level1 문제다 

어려웠던 문제. 

생각해본 문제풀이 로직은 처음에 빨간 구슬과 파란 구슬의 위치를 저장한 다음에 

bfs를 통해서 빨강과 파랑의 위치를 변경하는데, 변경하는 방법은 while문으로 #나 0 를 만나기 전까지 위치를 움직인다 

움직인 다음에 해당 위치에서 파란색은 0에 없고, 빨간색이 0인 경우에 움직인 횟수를 출력한다

아닌 경우에 -1을 출력한다 

 

여기서 간과한 것은 빨간 구슬과 파란 구슬이 겹칠 수도 있다는 것이다. 

이를 고려해서 위치를 움직일 때 각 구슬이 움직인 칸수를 구해서 더 많이 움직인 구슬의 위치를 한칸씩 뒤로 하는 것이다. (이 부분은 사실 정확히 이해가 가지 않는다)

 

빨간 구슬과 파란 구슬이 방문하지 않은 곳에 대해서 방문처리를 해주고 큐를 진행한다 

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
rx,ry,bx,by=0,0,0,0
visit=[[[[0]*m for _ in range(n)]for _ in range(m)] for _ in range(n)]

for i in range(n):
    data.append(list(input()))
    for j in range(m):
        if data[i][j]=='R':
            rx,ry=i,j
        if data[i][j]=='B':
            bx,by=i,j

def move(i,j,dx,dy):
    count=0
    while data[i+dx][j+dy]!='#' and data[i][j]!='O':
        count+=1
        i+=dx
        j+=dy
        count+=1
    return i,j,count

def bfs():
    while queue:
        ri,rj,bi,bj,result=queue.popleft()
        if result >10:
            break
        for i in range(4):
            nri,nrj,rc=move(ri,rj,dx[i],dy[i])
            nbi,nbj,bc=move(bi,bj,dx[i],dy[i])
            if data[nbi][nbj]!='O':
                if data[nri][nrj]=='O':
                   return result
                if nri==nbi and nrj == nbj: #파란구슬, 빨간구슬이 겹치는 경우
                    if rc > bc:
                        nri-=dx[i]
                        nrj-=dy[i]
                    else:
                        nbi-=dx[i]
                        nbj-=dy[i]
                if not visit[nri][nrj][nbi][nbj]:
                    visit[nri][nrj][nbi][nbj]=1
                    queue.append((nri,nrj,nbi,nbj,result+1))
    return -1
    
queue=deque()
queue.append((rx,ry,bx,by,1))
visit[rx][ry][bx][by]=1
dx=[-1,1,0,0]
dy=[0,0,-1,1]

print(bfs())