Python/BFS BOJ-13460 구슬탈출 2

Posted on | In

[Python/BFS] BOJ-13460 구슬탈출 2

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는 지 출력하라.

만약 10 번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

구슬 2개가 동시에 움직이기 때문에 4차원배열을 이용해 방문 여부를 체크하면 편하다.

실패 경우의 수

  1. 파란구슬이 구멍에 빠지는 경우

  2. 빨간 & 파란구슬이 구멍에 빠지는 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
N,M = map(int,input().split())
board = [list(map(str ,input().rstrip()))for _ in range(N)] # N 가로 / M 세로

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

# [rx][ry][bx][by] 방문여부 체크
visited = [[[[False]*M for _ in range(N)]for _ in range(M)] for _ in range(N)]

def pos_init():
    rx, ry, bx, by = 0,0,0,0
    for x in range(N) :
        for y in range(M):
            if board[x][y]=='R' :
                rx, ry= x,y
            elif board[x][y]=='B' :
                bx,by=x,y
    queue.append((rx,ry,bx,by,1))
    visited[rx][ry][bx][by] = True

def move(x,y,dx,dy):
    cnt = 0 
    while board[x+dx][y+dy] !='#' and board[x][y] !='O':
        x+=dx; y+=dy; cnt+=1
    return x,y,cnt

def bfs():
    pos_init()
    while queue:
        rx,ry,bx,by,depth =queue.pop(0)
        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 board[nbx][nby] !='O':
                if board[nrx][nry] == 'O':
                    print(depth)
                    return
                # 빨간 & 파란구슬이 같은 위치에 존재할 경우, 이동거리가 많은 것을 한칸 뒤로 이동
                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))
    print(-1)
bfs()

Reference

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

풀이참고 : https://rebas.kr/724