[파이썬][백준 13460][BFS] 구슬 탈출 2 - 컴도리돌이

---

13460번: 구슬 탈출 2

---

풀이 방법

 

1. 일단 알고리즘은 BFS를 사용하였다.

2. 큐에는 빨간색 공의 좌표(rx, ry)와 파란색의 공의 좌표(bx, by) 그리고 이동 횟수를 포함하고 있다.

3. 이동 횟수가 10이 넘어가면 break 시키고 -1 값을 반환해주었다.

4. 방문 표시는 빨간색의 공과 파란색의 공을 str으로 변환해주어서 dict에 True로 삽입하여 방문 표시를 체크하였다.

5. 상하좌우 4개의 방향으로 move 함수를 통해서 이동했을 때 위치가 '#'이 되기 전의 좌표 또는 이동 후에 위치가 'O' 일 경우 해당 이동했던 좌표 값과 몇 번 이동했는지 cnt를 반환해주었다.

6. 만약 파란색 공의 위치가 통로 위치일 경우 continue를 시켜주었다.

7. 만약 빨간색 공의 위치가 통로 위치일 경우 이동 횟수 +1을 반환시켜주었다. (끝)

8. 만약 빨간색 공의 좌표와 파란색 공의 좌표가 같을 경우 각각의 이동 횟수를 비교해서 위치를 조정해주었다.

예를 들면)

 

# . . . . . BR# 일 경우,

왼쪽(<-) 방향으로 move를 시켜주면,

# BR  . . . . .#

이렇게 반환 처리 되는데,

 

여기서 파란 공의 이동 횟수는 5번이고 빨간 색공의 이동 횟수는 6번이기 때문에 이동 횟수가 더 많은 공의 좌표 값을 이동 횟수 1회 빼준다.

 

---

풀이 코드

import sys; from collections import deque

# 입력 초기화
def init(r,c) :
  red = [] ; blue = [] ; board = []
  for i in range(r) :
    tmp = list(sys.stdin.readline().strip())
    for j in range(c) :
      if tmp[j] == 'R' :
        red = [i,j]
      if tmp[j] == 'B' :
        blue = [i,j]
    board.append(tmp)
  return board,red,blue

# 상화좌우 방향에 따른 이동 함수 
def move(x,y,i,c) :
  while arr[x+dx[i]][y+dy[i]] != '#' and arr[x][y] != 'O' :
    x += dx[i]
    y += dy[i]
    c += 1
  return x,y,c

# 너비 우선 탐색
def bfs() :
  q = deque()
  # 빨간 색 공의 좌표, 파란 색 공의 좌표 , 이동횟수
  q.append([red[0],red[1],blue[0],blue[1],0])
  # 초기 빨간 색 공 좌표와 파란 색 공 좌표 방문 처리
  visited = {str(red[0]) + str(red[1]) + str(blue[0]) + str(blue[1]) : True}
  while q :
    rx,ry,bx,by,cnt = q.popleft()
    #이동 횟수가 10이상일 경우 BREAK
    if cnt >= 10 :
      break
    for i in range(4) :
      nrx,nry,rc = move(rx,ry,i,0)
      nbx,nby,bc = move(bx,by,i,0)
      # 파란 색 공이 통로일 경우 PASS
      if arr[nbx][nby] == 'O' :
        continue
      # 빨간 색 공이 통로일 경우 RETURN
      if arr[nrx][nry] == 'O' :
        return cnt + 1
      # 파란 색 공과 빨간 색 공의 좌표가 같을 경우 -> 서로 이동 횟수 비교
      if nrx == nbx and nry == nby :
        if rc > bc :
          nrx -= dx[i]
          nry -= dy[i]
        else :
          nbx -= dx[i]
          nby -= dy[i]
      # 방문 표시
      route = str(nrx) + str(nry) + str(nbx) + str(nby)
      if route in visited :
        continue
      visited[route] = True
      q.append([nrx,nry,nbx,nby,cnt+1])
  return -1

n,m = map(int,sys.stdin.readline().split())
arr,red,blue = init(n,m)
arr[red[0]][red[1]] = '.'
arr[blue[0]][blue[1]] = '.'
dx = [0,0,-1,1]
dy = [1,-1,0,0]
print(bfs())