[백준 13460번] 구슬 탈출 2 - python

문제 링크

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

13460번: 구슬 탈출 2

풀이 

- bfs + 구현 문제 

1. 처음 빨간 구슬과 파란 구슬의 위치 rx, ry, bx, by에 저장 후 bfs 실행 

 

2. bfs 실행 

- visited = {} 에 빨간 구슬 위치과 파란 구슬의 위치를 key, 굴린 횟수 value로 저장

만약 visted[rx,ry,bx,by]의 value 값이 10보다 크거나 같으면 10번 이하로 움직여서 빨간 구슬을 빼낼 수 없다는 것이므로

-1 출력하고 return

- 위, 아래, 왼쪽, 오른쪽에 대하여 move 함수 실행

 

3. move 실행

- 벽이 아닐 때까지 한 방향으로 계속 이동

- m_count 에는 이동한 횟수 저장

- 만약 이동 중에 구멍을 만나면 0,0,0 리턴

- 벽까지 이동했으면 현재 위치와 이동한 횟수 리턴

 

4. bfs

- 두 공 모두 구멍을 통해 빠져나갔거나 파란공만 구멍을 통해 빠져나가면 안되므로 continue 

- 빨간공만 구멍을 통해 빠져나갔으면 visited 값  +  1 한 값 출력하고 리턴 

- 빨간공과 파란공의 위치가 같으면 안되므로 같으면 이동한 횟수가 더 큰 공이 마지막에 이동했다는 것이므로 한 칸 뒤로 이동 

- 굴린 위치가 방문하지 않은 곳이면 visited에 굴린 횟수 + 1 추가 , 큐에 추가

- 만약 리턴하지 않고 큐를 빠져나왔으면 구멍을 통해 빼낼 수 없다는 것이므로 -1 출력하고 리턴 

from collections import deque 

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

def move(x,y,mx,my):
  m_count = 0 
  while graph[x+mx][y+my] != '#':
    if graph[x+mx][y+my] =='O':
      return 0, 0, 0
    x += mx
    y += my
    m_count += 1 

  return x, y, m_count
  
def bfs(rx,ry,bx,by):
  visited = {}
  # 방문 표시, 굴린 횟수 0 
  visited[rx,ry,bx,by] = 0 

  q = deque()
  q.append((rx,ry,bx,by))

  while q :
    
    rx, ry, bx, by = q.popleft()

    # 굴린 횟수가 10 이상이면 
    if visited[rx,ry,bx,by] >= 10 :
      print(-1)
      return 

    for i in range(4):
      # 한 방향으로 굴리기 
      nrx, nry, rmove = move(rx,ry,dx[i],dy[i])    
      nbx, nby, bmove = move(bx,by,dx[i],dy[i])

      # 두 공 모두 탈출했거나 파란 공만 탈출한 경우 무시 
      if not nbx and not nby :
        continue
      # 빨간 공만 탈출한 경우 
      elif not nrx and not nry:
        # 굴린 횟수 출력 
        print(visited[rx,ry,bx,by]+1)
        return 
      # 빨간 공과 파란 공의 위치가 같다면 
      elif nrx == nbx and nry == nby :
        # 더 많이 이동한 공 한칸 뒤로 이동 
        if rmove > bmove:
          nrx -= dx[i]
          nry -= dy[i]
        else:
          nbx -= dx[i]
          nby -= dy[i]
      # 방문 기록 표시 
      if (nrx,nry,nbx,nby) not in visited :
        visited[nrx,nry,nbx,nby] = visited[rx,ry,bx,by]+1
        q.append((nrx,nry,nbx,nby))
  # 리턴하지 않고 끝났다면 구멍을 통해 빼낼 수 없다는 뜻이므로
  print(-1)
  return 
    
n, m = map(int,input().split())

graph = []

for _ in range(n):
  graph.append(list(input()))

# 처음 빨간 공, 파란 공 위치 기록 
rx, ry, bx, by = 0,0,0,0
for i in range(n):
  for j in range(m):
    if graph[i][j] == 'R':
      rx = i
      ry = j
    if graph[i][j] == 'B':
      bx = i
      by = j

bfs(rx,ry,bx,by)

- 구현 문제를 많이 풀어봐야겠다. 푸는 건 재밌는데 시간이 너무 오래 걸린다 ㅠㅠ