백준(BOJ) 13460 구슬 탈출 2(Python)

문제 내용

 

BFS 문제.

18170이랑 비슷하게 두 개의 요소를 고려하는 BFS 문제였다.

거기다가 좌표를 한 번에 여러 칸 이동해야 했기 때문에 고려할 부분이 많았다.

먼저 빨간 공을 움직이는데, 움직일 자리에 파란 공이 있을 때 파란 공도 움직일 수 있다면 둘 다 움직이고, 그렇지 않다면 break한다.

이때 파란 공이 움직여서 구멍에 도착했는지 확인하고, 구멍에 도착했다면 continue한다.

만약 빨간 공이 움직일 자리에 파란 공이 없다면 계속 움직인다.

빨간 공이 구멍에 도착했다면 flag를 수정하고, 파란 공을 마저 움직인다.

이때 파란 공이 구멍에 도착했다면 continue하고, 그렇지 않다면 횟수를 출력하고 break한다.

만약 빨간 공이 구멍에 도착하지 않은 상태라면 visited에 두 공의 좌표를 추가한다.

처음에는 빨간 공과 파란 공의 visited를 따로 갱신하면서 알고리즘을 짰는데, 이 문제는 두 공이 동시에 같은 좌표에 있었는가가 중요한 문제인 것 같아 하나의 visited에 두 공의 좌표를 모두 담은 리스트를 append하고, 현재 두 공의 좌표를 담은 리스트가 visited에 존재하는지를 체크했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[]
Rx=0
Ry=0
Bx=0
By=0
Gx=0
Gy=0
dx=[1,-1,0,0]
dy=[0,0,1,-1]
for i in range(n):
    x=list(input())
    X=[]
    for j in range(len(x)):
        if x[j]=='B':
            X.append(0)
            Bx=i
            By=j
        elif x[j]=='R':
            X.append(0)
            Rx=i
            Ry=j
        elif x[j]=='O':
            X.append(0)
            Gx=i
            Gy=j
        elif x[j]=='.':
            X.append(0)
        else:
            X.append(1)
    L.append(X)
queue=deque([])
queue.append([0,Rx,Ry,Bx,By])
visited=[]
visited.append([Rx,Ry,Bx,By])
flag=0
while queue:
    t,x1,y1,x2,y2=queue.popleft()
    flag4=0
    if t>=10:
        break
    for i in range(4):
        nx1=x1
        ny1=y1
        nx2=x2
        ny2=y2
        flag2=0
        flag3=0
        while not L[nx1+dx[i]][ny1+dy[i]]:
            if nx1+dx[i]==nx2 and ny1+dy[i]==ny2:
                if not L[nx2+dx[i]][ny2+dy[i]]:
                    nx2+=dx[i]
                    ny2+=dy[i]
                    nx1+=dx[i]
                    ny1+=dy[i]
                    if nx2==Gx and ny2==Gy:
                        flag2=1
                        break
                else:
                    break
            else:
                nx1+=dx[i]
                ny1+=dy[i]
                if nx1==Gx and ny1==Gy:
                    nx1=0
                    ny1=0
                    flag3=1
                    break
        if flag2:
            continue
        while not L[nx2+dx[i]][ny2+dy[i]]:
            if nx2+dx[i]==nx1 and ny2+dy[i]==ny1:
                break
            nx2+=dx[i]
            ny2+=dy[i]
            if nx2==Gx and ny2==Gy:
                flag2=1
                break
        if flag2:
            continue
        if flag3:
            flag4=1
            print(t+1)
            break
        if [nx1,ny1,nx2,ny2] not in visited:
            visited.append([nx1,ny1,nx2,ny2])
            queue.append([t+1,nx1,ny1,nx2,ny2])
    if flag4:
        flag=1
        break
if not flag:
    print(-1)

 

움직인 횟수를 잘못 처리해서 맞왜틀 하고 있었다.

금방 풀 수 있을 것 같았는데 은근히 오래 걸렸다.