[백준 13460번] 구슬탈출 2(파이썬)

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

이 문제는 여타 길찾기 문제와는 다른점.

한번 움직이면 벽을 만날 때까지 이동한다는 것.

즉, 만약에 오른쪽으로 움직인다고 하면

벽을 만나기 전까지 계속 오른쪽으로 가야합니다.

 

이 문제에서 어려웠던 포인트는

 

1. 파란색이 구멍에 들어갈 땐 어떻게??

 

2. 파란색공과 빨간색공이 겹치면 안되는데

이건 어떻게 구현하지??

 

https://wlstyql.tistory.com/72

백준 알고리즘 13460 (구슬 탈출 1,2) - python

저는 이분의 해설을 많이 참고했습니다.

이 분 같은 경우에는

vistied를 4차원으로 받아

빨간색공, 파란색공

각각의 좌표를 받았네요.

 

그리고 빨간색과 파란색 좌표가 같을 경우

움직임이 많았던 것의 움직임을 빼주는 식인데요

그림을 그려보면 이해가 어느정도 갑니다.

R B인 상태로

오른쪽으로 쭉 이동하면

R B가 나중에 겹치는데

이 때, R이 B보다 더 많이 이동했으므로

R이 이동한 걸 -1해주면

자연스럽게 

RB로 분리가 됩니다.

 

# 백준13460 구슬탈출2
from collections import deque

N, M = map(int, input().split())
B = []
rx = 0
ry = 0
bx = 0
by = 0
for i in range(N):
    data = list(input().rstrip())
    B.append(data)
    for j in range(M):
        if data[j] == 'R':
            rx, ry = i, j
        if data[j] == 'B':
            bx, by = i, j

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = deque()
queue.append((rx, ry, bx, by, 1))

visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]


def move(x, y, dx, dy):
    cnt = 0

    while B[x + dx][y + dy] != '#' and B[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt


while queue:
    go = 0
    rx, ry, bx, by, depth = queue.popleft()
    if depth > 10:
        break
    for i in range(4):
        nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
        nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
        if B[nbx][nby] != 'O':
            if B[nrx][nry] == 'O':
                go = 1
                break
            if nrx == nbx and nry == nby:
                if rcnt > bcnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                queue.append((nrx, nry, nbx, nby, depth + 1))
    if go == 1:
        print(depth)
        break

if go == 0:
    print(-1)

 

 

4차원배열을 써서 다소 정신이 없다고 느끼신다면

편안하게 2차원배열을 마련해서

빨간색,파란색 각각에 다해서 넣으셔도 될 것 같습니다.

 

+++

DFS를 사용한 풀이도 있습니다.

#백준 13460번 구슬탈출 2

N,M=map(int,input().split())

graph=[]
bx=0
by=0
rx=0
ry=0


dx=[0,0,1,-1]
dy=[1,-1,0,0]

for i in range(N):
    data=list(input().rstrip())
    graph.append(data)

    for j in range(M):
        if data[j]=='B':
            bx=i
            by=j
        if data[j]=='R':
            rx=i
            ry=j

def move_ball(x,y,d):
    cnt=0
    while graph[x+dx[d]][y+dy[d]]!='#' and graph[x][y]!='O':
        x+=dx[d]
        y+=dy[d]
        cnt+=1

    return x,y,cnt

answer=11

def dfs(bx,by,rx,ry,time):
    global answer
    if time>10:
        return

    b_cnt=0
    r_cnt=0
    #상하좌우로 움직여준다
    for d in range(4):
        nbx,nby,b_cnt=move_ball(bx,by,d)
        nrx,nry,r_cnt=move_ball(rx,ry,d)

        #파란색이 홀에 담기면 실패
        if graph[nbx][nby]=='O':
            return
        #빨간색이 홀에 담기면 게임 끝
        if graph[nrx][nry]=='O':
            answer=min(answer,time)
            return

        # 빨간색과 파란색이 서로 겹칠 경우
        # 많이 움직인걸 뒤로 빼준다
        if nbx==nrx and nby==nry:
            if b_cnt>r_cnt:
                nbx-=dx[d]
                nby-=dy[d]
            elif b_cnt<r_cnt:
                nrx-=dx[d]
                nry-=dy[d]



        dfs(nbx,nby,nrx,nry,time+1)

time=1
dfs(bx,by,rx,ry,time)

if answer==11:
    print(-1)
else:
    print(answer)

이 풀이방식은

위의 방식보다

시간이 더 오래걸리긴 했습니다.

다양한 관점으로 문제를 볼 때

참고하시면 좋을 듯합니다.