[py] 삼성 - 구슬탈출2 (BFS,조건)

문제

문제링크
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
R - 빨간 구슬
B - 파란 구슬

풀이

• 4차원 배열 이용 check

• Queue에 빨간 구슬의 (X, Y) 좌표, 파란 구슬의 (X, Y) 좌표를 모두 넣는다.
  방문 여부를 확인할 check 배열을 4차원 배열로 선언한다. 배열의 인덱스는 [빨간 X좌표][빨간 Y좌표] [파란 X좌표][파란 Y좌표] 이다.

• 구슬을 굴릴 때, 구슬의 다음 위치가 벽(#)인지, 구슬의 현재 위치가 구멍(O)인지 확인한다.

• 구슬의 다음 위치가 벽이라면 앞으로 가지 못한다. 구슬의 현재 위치가 구멍이라면, 현재 구슬의 색이 무엇인지 판별한다.
  만약 파란 구슬의 현재 위치가 구멍이라면 무시하고, 빨간 구슬의 현재 위치가 구멍이라면, 1을 출력하고 종료한다.

• 구슬을 굴리면서, 빨간 구슬의 이동 거리와 파란 구슬의 이동 거리를 카운트해야 한다.

• 구슬을 굴린 후, 빨간 구슬의 위치와 파란 구슬의 위치가 같다면, 이동 거리 비교를 통해 겹치지 않도록 처리해야 한다.
  만약 구슬이 겹쳤다면, 굴릴 때 카운트했던 이동 거리가 더 긴 구슬의 위치를 한 칸 이전으로 되돌린다.

• 굴리는 과정이 10번을 넘어가면 그대로 종료하고, 0을 출력한다.
  더 이상 갈 곳이 없을 때에는 BFS를 빠져나와서 0을 출력한다.

코드

dx = [-1, 1, 0, 0]  # x축 움직임
dy = [0, 0, -1, 1]  # y축 움직임
queue = deque()  # BFS : queue 활용
check = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
print(a)
def init():
    _rx, _ry, _bx, _by = [0]*4
    for i in range(N):
        for j in range(M):
            if a[i][j] == 'R':
                _rx, _ry = i, j
            elif a[i][j] == 'B':
                _bx, _by = i, j
    queue.append((_rx, _ry, _bx, _by, 1))  #마지막 횟수저장
    check[_rx][_ry][_bx][_by] = True
    test = move(1, 4, 0, -1, 0)
    #print(test)
def move(_x, _y, _dx, _dy, _c):
    #print(_x, _y, _dx, _dy, _c , "벽",a[_x+_dx][_y+_dy])
    while a[_x+_dx][_y+_dy] != '#' and a[_x][_y] != 'O':
        _x += _dx
        _y += _dy
        _c += 1  # 움직인 거리
    return _x, _y, _c
def bfs():
    while queue:
        rx, ry, bx, by, d = queue.popleft()
        # 10이상될경우 -1로 값출력
        if d >= 10:
            break
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0)  #rc 거 리
            nbx, nby, bc = move(bx, by, dx[i], dy[i], 0)  #bc 거 리
            # 파란공 탈출 경우 - continue를 함으로써 queue에 값을 넣지 않고 넘어간다.~!
            if a[nbx][nby] == 'O':
                continue
            # 결과 출력 (빨강공 탈출)
            if a[nrx][nry] == 'O':
                print(d)
                return
            # 빨강공 파랑공 위치겹치는경우
            if nrx == nbx and nry == nby:
                if rc > bc:
                    nrx, nry = nrx-dx[i], nry-dy[i]
                else:
                    nbx, nby = nbx-dx[i], nby-dy[i]
            if not check[nrx][nry][nbx][nby]:
                check[nrx][nry][nbx][nby] = True
                queue.append((nrx, nry, nbx, nby, d+1))
    print(-1) 
init()
#bfs()