[ BOJ ] 구슬 탈출 2

/  구현 1  /

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]

for i in range(n):
  for j in range(m):
    if board[i][j] == 'R':
      red = [i, j]
    elif board[i][j] == 'B':
      blue = [i, j]
    elif board[i][j] == 'O':
      hole = [i, j]

movePossible = True
count = 0

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

def roll(i, ball):
  nx = ball[0] + dx[i]
  ny = ball[1] + dy[i]
  if board[nx][ny] != '#':
    return [nx, ny]
  else:
    return False

while red != hole or movePossible:
  # 왼/ 오/ 위/ 아 굴리기
  dist = n + m
  newRed = red
  newBlue = blue
  for i in range(4):
    nred = roll(i, red)
    nblue = roll(i, blue)
    # 굴리는거 가능하면
    if nred and nblue:
      # red-hole 거리 계산
      ndist = abs(hole[0] - nred[0]) + abs(hole[1] - nred[1])
      movePossible = True
    else:
      movePossible = False
    # 최소 거리 갱신 
    if movePossible:
      dist = min(dist, ndist)
      newRed = nred
      newBlue = nblue
  # 최소 거리인 방향으로 red, blue 이동
  red = newRed
  blue = newBlue
  # count += 1
  count += 1

# if red == hole and blue == hole :blue도 동시에 빠진거나 count가 10보다 크면 -1 출력  // 아니면 count 출력
if blue == hole or 10 <= count :
  print(-1)
else:
  print(count)

 

: 무한 루프가 뜹니다.

 

아마 나가는 조건을 잘 못 설정했던지 한 것 같습니다. 

구현 문제를 거의 3주만에 접하니 머리가 안 돌아갑니다. 역시 꾸준함이 중요한 것 같습니다.

구현 문제는 매일 풀되, 거기에 얹어서 알고리즘을 적용한 문제를 같이 풀어야겠습니다.

 

---

널리 퍼진 정석적인 풀이 알고리즘이 존재하는 것 같습니다.

 

하지만, 연습하신 분들 별로 풀이가 미묘하게 달라 3-4분의 코드를 확인하였고,

 

가장 이해 쉽게 설명하신 코드를 보고 정리하였습니다.

https://rebas.kr/724

BOJ 13459 · 구슬 탈출

 

/  남의 풀이  /

 

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()

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
    q.append((_rx, _ry, _bx, _by, 0))
    check[_rx][_ry][_bx][_by] = True

def move(_x, _y, _dx, _dy, _c):
    while a[_x+_dx][_y+_dy] != '#' and a[_x][_y] != 'O':
        _x += _dx
        _y += _dy
        _c += 1
    return _x, _y, _c

def bfs():
    while q:
        rx, ry, bx, by, d = q.popleft()
        if d >= 10:
            break
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0)
            nbx, nby, bc = move(bx, by, dx[i], dy[i], 0)
            if a[nbx][nby] == 'O':
                continue
            if a[nrx][nry] == 'O':
                print(d+1)
                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
                q.append((nrx, nry, nbx, nby, d+1))
    print(-1)

init()
bfs()