[백준] 13460번 파이썬 _ 구슬 탈출 (삼성SW)

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

13460번: 구슬 탈출 2

 

문제유형 : 구현(시뮬레이션), BFS

 

문제풀이 : 

• 방문처리할 배열을 4차원으로 정의한다. (빨간구슬과 파란구슬을 함께 체크하기위함)
  • check[rx][ry][bx][by] = True 이런식으로
• 초기의 빨간구슬과 파란구슬의 위치를 큐에 삽입
• bfs함수를 통해, 빨간구슬과 파란구슬 모두 위,아래,왼,오른쪽으로 이동하는데 벽(#)이거나 구멍(O) 전까지 직진
  • 이때 파란구슬이 구멍을 만나면 실패이므로 파란애가 구멍을 만나지 않을때 체크 필요 
• 만약에 빨간구슬과 파란구슬이 겹쳐졌다는것은 하나는 막혀서 멈춰있는데 하나가 다가온것이므로 이럴경우 더 늦게 도착한애를 하나 뒤로 움직여줘야한다. (이것을 위해 구슬의 이동거리를 세줘야함)

정답코드:

def init(graph,n,m):
    rx,ry,bx,by = 0,0,0,0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                rx,ry = i,j
            elif graph[i][j] == 'B':
                bx,by = i,j
    q.append((rx,ry,bx,by,1))
    check[rx][ry][bx][by] = True

#현재의 좌표 x,y // 이동할만큼의 거리 dx,dy
def move(x,y,dx,dy):
    cnt = 0
    # 현재내위치의 인접이 벽이거나, 내위치가 구슬이면 이동안하도록
    # 즉 move함수를 수행했을때 구슬의위치는 구멍 위거나 벽 바로옆
    while graph[x+dx][y+dy] != '#' and graph[x][y] != 'O':
        x += dx
        y += dy
        cnt +=1
    return x,y,cnt

def bfs(graph, n,m):
    init(graph, n,m)
    while q:
        rx,ry,bx,by, depth = q.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 graph[nbx][nby] != 'O':
                # 빨간구슬이 구멍위라면 끝
                if graph[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 check[nrx][nry][nbx][nby]:
                    check[nrx][nry][nbx][nby] = True
                    q.append((nrx,nry,nbx,nby, depth+1))
    print(-1)


import sys
from collections import deque

input = sys.stdin.readline

if __name__ == '__main__':
    # 가로(열), 세로(행) - m,n

    graph = []
    n,m = map(int, input().split())

    for i in range(n):
        temp = list(input().strip())
        graph.append(temp)

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

    q = deque()

    # 방문처리해줄 4차원 배열
    check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]

    bfs(graph,n,m)

 

걸린시간 : 2시간고민 -> 풀이참조