4/13 Coding Test

✅ 문제풀이 - BOJ (그래프 탐색)

🎈 13460 구슬 탈출 2 (실패)

구슬 탈출은 직사각형 보드에 빨간 구슬 ,파랑 구슬을 하나씩 넣은 다음 빨간 구슬을 구멍을 통해 빼내는 게임으로 목표는 빨간 구슬을 구멍을 통해 뺴내는 것이고 파란 구슬이 구멍에 들어가도록 해선 안된다. 구멍으로 빼내는 과정은 위, 아래, 오른쪽, 왼쪽으로 기울이는 방법으로 빨간 구슬, 파란 구슬은 동시에 같은 칸에 있을 수 없다. 위 과정을 거쳐 최소 몇 번만에 빨간 구슬을 빼내는 지 구하는 문제.

• 조건은 다음과 같다.
  빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

입출력은 다음과 같다.

• 입력 : 첫 줄에 보드 세로, 가로를 의미하는 n, m이 주어지고 다음 n줄에 보드 모양을 나타내는 길이 m의 문자열이 주어진다. 문자열에서 .는 빈칸, #은 벽, O는 구멍 위치, R은 빨간 구슬 위치, B는 파란 구슬 위치이다. 입력되는 보드의 가장자리에는 모두 벽이 존재하고 구멍 개수, 빨간 구슬, 파란 구슬 개수는 항상 1개로 주어진다.
• 출력 : 빨간 구슬을 구멍으로 빼낼 수 있는 최소 횟수를 구하는 문제로 10번 이하로 움직여서 빨간 구슬을 뺄 수 없으면 -1을 출력한다.

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(n)]
# 생성한 그래프에서 빨간 구슬, 파란 구슬 시작점 각각 저장
for i in range(n):
    for j in range(len(graph[0])):
        if graph[i][j] == 'R':
            rx, ry = i, j
            graph[i][j] = '.'
        elif graph[i][j] == 'B':
            bx, by = i, j
            graph[i][j] = '.'
# 기울임 표시를 위해 moving 함수 제작 (한 칸이 아니고 벽까지 이동하는 것을 구현)
def moving(x, y, dx, dy):
    nx, ny = x, y
    move_cnt = 0
    while True:
        if graph[nx + dx][ny + dy] != '#' and graph[nx + dx][ny + dy] != 'O':
            move_cnt += 1
            nx += dx
            ny += dy
        else:
            break
    return nx, ny, move_cnt

def bfs():
    queue = deque()
    queue.append((rx, ry, bx, by, 0))
    while queue:
        red_x, red_y, blue_x, blue_y, cnt = queue.popleft()
        # 10번 넘어가면 건너 뛰고 -1 리턴
        if cnt > 10:
            continue
        # 상하 좌우 4방향 탐색 실시 (빨간 구슬, 파란 구슬 모두)
        for i in range(4):
            nrx, nry, rmove = moving(red_x, red_y, dx[i], dy[i])
            nbx, nby, bmove = moving(blue_x, blue_y, dx[i], dy[i])
            # 다음 이동으로 파란 구슬이 구멍에 들어가면 리턴하도록 건너뛰기
            if graph[nbx+dx[i]][nby+dy[i]] == 'O':
                continue
            if graph[nrx+dx[i]][nry+dy[i]] == 'O':
                return cnt + 1
            # 다음 위치가 현재 위치랑 동일함 즉, 기울였을 때 더 이상 이동이 없으면 건너 뛰기
            if nrx == red_x and nry == red_y and nbx == blue_x and nby == blue_y:
                continue
            # 파란 구슬 빨간 구슬 위치 같은 경우
            if nrx == nbx and nry == nby:
                if rmove > bmove:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
            
    return -1

print(bfs())

< 풀이 과정 >
기존 BFS 풀이에서 한 칸 씩 이동하는 방식을 while문을 통해 기울이는 방식으로 표현하는 과정을 구현하기 위해 새로운 함수 moving 을 짜느라 오래 걸렸다😭

어느 부분에서 오류가 나는지 오늘 안으로 반례를 찾지 못했다..
🧨 위 방식에서 60%가 넘어가면 실패케이스가 나온다.. 추후 꼭 다시 풀어볼 문제!