[백준 13459] 구슬 탈출

1. 문제

www.acmicpc.net/problem/13459

13459번: 구슬 탈출

2. 접근 방법

BFS로 풀어야합니다.

 

1. Queue에 red, blue 구슬 좌표를 append한다.

2. 방문 여부 확인할 check배열을 4차원 배열로 선언한다.

2-1. check = [red_y][red_x][blue_y][blue_x]

3. 구슬 굴린다.

3-1. 구슬의 다음 위치가 벽인지, 구슬의 현재 위치가 구멍인지 확인

3-2. 만약 구슬의 다음 위치가 벽이라면 앞으로 못간다.

3-3. 구슬의 현재 위치가 구멍이라면 현재 색이 무엇인지 판별한다.

3-3-1. 구슬의 현재 위치가 구멍이고, 파란색이라면 pass

3-3-2. 구슬의 현재 위치가 구멍이고, 빨간색이라면 1을 출력하고 종료시킨다.

4. 구슬을 굴리면서 빨간 구슬의 이동거리와 파란 구슬의 이동거리를 카운트센다.

5. 구슬 굴린 후 빨간 구슬과 파란 구슬의 위치가 같다면, 이동거리 비교를 통해 겹치지 않도록 처리해준다.

5-1. 만약 겹쳤다면 굴릴 때 카운트 했던 이동 거리가 더 긴 구슬의 위치를 한 칸 이전으로 옮긴다.

6. 굴리는 과정이 10번을 넘어가면 그대로 종료하고 0을 출력한다.

7. 더이상 갈 곳이 없을 때는 BFS를 빠져나와 0을 출력한다.

3. 코드

python

from collections import deque

def move(_x, _y, _dx, _dy, _c):
    while board[_y + _dy][_x + _dx] != '#' and board[_y][_x] != '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 board[nby][nbx] == 'O':
                continue
            # 빨간 공이 구멍에 빠졌을 때 -> 종료
            if board[nry][nrx] == 'O':
                print(1)
                return
            # 만약 빨간 공과 파란 공의 위치가 같다면
            if nrx == nbx and nry == nby:
                # 카운트를 비교한다(1): 파란색이 더 먼저 도착했음 -> 빨간색이 온만큼 한 번 물러선다.
                if rc > bc:
                    nrx, nry = nrx - dx[i], nby - dy[i]
                # 카운트를 비교한다(2): 빨간색이 더 먼저 도착했음 -> 파란색이 온만큼 한 번 물러선다.
                else:
                    nbx, nby = nbx - dx[i], nby - dy[i]
            # 만약 방문하지 않은 곳이라면
            if not check[nry][nrx][nby][nbx]:
                # 방문 체크하고
                check[nry][nrx][nby][nbx] = True
                # 다시 BFS
                q.append((nrx, nry, nbx, nby, d + 1))
    print(0)

N, M = map(int, input().split())
board = [list(input()) 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()

_rx, _ry, _bx, _by = [0] * 4
for y in range(N):
    for x in range(M):
        if board[y][x] == 'R':
            _rx, _ry = x, y
        elif board[y][x] == 'B':
            _bx, _by = x, y

# 초기 상태 append
q.append((_rx, _ry, _bx, _by, 0))
# 초기 visit 체크
check[_ry][_rx][_by][_bx] = True

bfs()

4. 마치며

구슬 두개를 한 번에 굴릴 때는 방문 체크할 때 4차를 쓴다는 것을 처음 깨달았다 ㅜ.ㅜ

ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

화이팅 나 자신