[Gold I] 구슬 탈출 - 13459

문제 링크

성능 요약

메모리: 35472 KB, 시간: 64 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 격자 그래프

문제 설명

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

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

보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력한다.

---

문제 풀이

문제 분석

이 문제는 주어진 보드에서 빨간 구슬을 구멍을 통해 빼내는 최소 횟수를 구하는 문제입니다. 단, 파란 구슬이 구멍에 들어가면 안 되며, 최대 10번의 이동 안에 빨간 구슬을 빼내야 합니다. 입력으로는 보드의 크기와 보드 상태가 주어지고, 출력으로는 성공하면 1, 실패하면 0을 출력해야 합니다.

접근 방법

이 문제는 BFS (너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 현재 상태에서 가능한 모든 다음 상태를 탐색하며, 목표 상태에 도달할 때까지 탐색을 반복합니다.

1. 상태 정의: 빨간 구슬과 파란 구슬의 위치를 하나의 상태로 정의합니다.
2. 큐 사용: 큐를 사용하여 탐색할 상태를 관리합니다.
3. 방문 여부 확인: 방문 여부를 확인하여 중복 탐색을 방지합니다.
4. 이동: 상, 하, 좌, 우로 기울이는 동작을 시뮬레이션합니다.
5. 종료 조건: 10번 이하로 빨간 구슬을 구멍에 빼내거나, 더 이상 탐색할 상태가 없을 때 종료합니다.

구현 설명

1. 입력 및 초기화

• 입력을 받고 보드 상태를 graph 리스트에 저장합니다.
• 빨간 구슬(R)과 파란 구슬(B)의 초기 위치를 찾고, graph에서 해당 위치를 빈 칸(.)으로 변경합니다.
• BFS 탐색을 위한 큐(stack)를 초기화하고, 시작 상태 (빨간 구슬 위치, 파란 구슬 위치, 이동 횟수)를 큐에 넣습니다.
• 방문 여부를 저장하기 위한 visited 집합을 초기화하고, 시작 상태를 visited에 추가합니다.

2. BFS 탐색

• 큐가 빌 때까지 다음을 반복합니다.
  • 큐에서 현재 상태 (빨간 구슬 위치, 파란 구슬 위치, 이동 횟수)를 꺼냅니다.
  • 이동 횟수를 1 증가시킵니다.
  • 이동 횟수가 10을 초과하면 탐색을 중단합니다.

3. 이동 시뮬레이션 (상, 하, 좌, 우)

• 각 방향으로 기울이는 동작을 시뮬레이션합니다.
  • 각 방향에 대해 빨간 구슬과 파란 구슬을 이동시킵니다.
  • 벽(#)이나 구멍(O)을 만날 때까지 이동합니다.
  • 빨간 구슬과 파란 구슬이 같은 위치에 있을 경우, 더 늦게 이동한 구슬을 한 칸 뒤로 이동시킵니다.
  • 이동 결과 빨간 구슬만 구멍에 빠졌다면 성공 (1을 출력)하고 종료합니다.
  • 파란 구슬이 구멍에 빠졌거나, 빨간 구슬과 파란 구슬이 동시에 구멍에 빠졌다면 실패 (다음 상태 탐색)합니다.

4. 방문 여부 확인 및 큐에 추가

• 이동 결과 생성된 새로운 상태가 visited에 없다면, visited에 추가하고 큐에 넣습니다.

⏱복잡도 분석

• 시간 복잡도: 최악의 경우 모든 상태를 탐색해야 하므로, O(N*M*N*M*4^10)입니다. N, M은 보드의 크기이며, 4는 이동 가능한 방향의 수, 10은 최대 이동 횟수입니다. 하지만 실제로는 방문 여부를 확인하며 탐색을 진행하므로, 이보다는 훨씬 빠릅니다.
• 공간 복잡도: visited 집합에 저장되는 상태의 수는 최대 O(N*M*N*M)이므로, 공간 복잡도는 O(N^2 * M^2)입니다.

핵심 포인트

1. BFS를 이용한 최적 이동 횟수 탐색: 최소 이동 횟수를 구해야 하므로 BFS를 사용하는 것이 적절합니다.
2. 구슬의 동시 이동 및 충돌 처리: 빨간 구슬과 파란 구슬이 동시에 움직이며, 같은 위치에 있을 수 없다는 조건을 정확히 구현해야 합니다.
3. 방문 여부 체크를 통한 중복 탐색 방지: visited 집합을 사용하여 이미 방문한 상태는 다시 탐색하지 않도록 하여 시간 효율성을 높입니다.

풀이 코드

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().strip()) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == "R":
            graph[i][j] = "."
            red = (i, j)
        if graph[i][j] == "B":
            graph[i][j] = "."
            blue = (i, j)

redhole = False
bluehole = False

stack = deque([(red, blue, 0)])
visited = set()
visited.add((red[0], red[1], blue[0], blue[1]))
cnt = 0

while stack:
    r, b, cnt = stack.popleft()
    cnt += 1
    if cnt > 10:
        break

    rx, ry = r[0], r[1]
    bx, by = b[0], b[1]

    # Left 이동
    i = 1
    withBlue = False
    bluehole = False 
    redhole = False
    while True:
        if rx == bx and ry - i == by:
            withBlue = True
        if graph[rx][ry - i] == ".":
            i += 1
        elif graph[rx][ry - i] == "O":
            redhole = True
            left_red = (rx, ry - i)
            break
        elif graph[rx][ry - i] == "#":
            left_red = (rx, ry - i + 1)
            break

    if withBlue:
        bluehole=True
        if not redhole:
            left_blue = left_red
            left_red = (left_red[0], left_red[1] + 1)
            if not (left_red[0], left_red[1], left_blue[0], left_blue[1]) in visited:
                visited.add((left_red[0], left_red[1], left_blue[0], left_blue[1]))
                stack.append((left_red, left_blue, cnt))
    else:
        i = 1
        while True:
            if graph[bx][by - i] == ".":
                i += 1
            elif graph[bx][by - i] == "O":
                bluehole = True
                break
            elif graph[bx][by - i] == "#":
                left_blue = (bx, by - i + 1)
                break
        if redhole and not bluehole:
            break
        
        if not bluehole:
            if left_red[0] == left_blue[0] and left_red[1] == left_blue[1]:
                left_blue = (left_blue[0], left_blue[1] + 1)

            if not (left_red[0], left_red[1], left_blue[0], left_blue[1]) in visited:
                visited.add((left_red[0], left_red[1], left_blue[0], left_blue[1]))
                stack.append((left_red, left_blue, cnt))

    # Right 이동
    i = 1
    bluehole = False
    withBlue = False
    redhole = False
   
    while True:
        if rx == bx and ry + i == by:
            withBlue = True
        if graph[rx][ry + i] == ".":
            i += 1
        elif graph[rx][ry + i] == "O":
            redhole = True
            right_red = (rx, ry + i)
            break
        elif graph[rx][ry + i] == "#":
            right_red = (rx, ry + i - 1)
            break

    if withBlue:
        bluehole=True
        if not redhole:
            right_blue = right_red
            right_red = (right_red[0], right_red[1] - 1)
            if not (right_red[0], right_red[1], right_blue[0], right_blue[1]) in visited:
                visited.add((right_red[0], right_red[1], right_blue[0], right_blue[1]))
                stack.append((right_red, right_blue, cnt))
    else:
        i = 1
        while True:
            if graph[bx][by + i] == ".":
                i += 1
            elif graph[bx][by + i] == "O":
                bluehole = True
                break
            elif graph[bx][by + i] == "#":
                right_blue = (bx, by + i - 1)
                break
        if redhole and not bluehole:
            break
        if not bluehole:
            if right_red[0] == right_blue[0] and right_red[1] == right_blue[1]:
                right_blue = (right_blue[0], right_blue[1] - 1)
            if not (right_red[0], right_red[1], right_blue[0], right_blue[1]) in visited:
                visited.add((right_red[0], right_red[1], right_blue[0], right_blue[1]))
                stack.append((right_red, right_blue, cnt))

    # Up 이동
    i = 1
    bluehole = False
    withBlue = False
    redhole = False
    while True:
        if rx - i == bx and ry == by:
            withBlue = True
        if graph[rx - i][ry] == ".":
            i += 1
        elif graph[rx - i][ry] == "O":
            redhole = True
            up_red = (rx - i, ry)
            break
        elif graph[rx - i][ry] == "#":
            up_red = (rx - i + 1, ry)
            break

    if withBlue:
        bluehole=True
        if not redhole:
            up_blue = up_red
            up_red = (up_red[0] + 1, up_red[1])
            if not (up_red[0], up_red[1], up_blue[0], up_blue[1]) in visited:
                visited.add((up_red[0], up_red[1], up_blue[0], up_blue[1]))
                stack.append((up_red, up_blue, cnt))
    else:
        i = 1
        while True:
            if graph[bx - i][by] == ".":
                i += 1
            elif graph[bx - i][by] == "O":
                bluehole = True
                break
            elif graph[bx - i][by] == "#":
                up_blue = (bx - i + 1, by)
                break
        if redhole and not bluehole:
            break
        if not bluehole:
            if up_red[0] == up_blue[0] and up_red[1] == up_blue[1]:
                up_blue = (up_blue[0] + 1, up_blue[1])
            if not (up_red[0], up_red[1], up_blue[0], up_blue[1]) in visited:
                visited.add((up_red[0], up_red[1], up_blue[0], up_blue[1]))
                stack.append((up_red, up_blue, cnt))

    # Down 이동
    i = 1
    bluehole = False
    withBlue = False
    redhole = False
    while True:
        if rx + i == bx and ry == by:
            withBlue = True
        if graph[rx + i][ry] == ".":
            i += 1
        elif graph[rx + i][ry] == "O":
            redhole = True
            down_red = (rx + i, ry)
            break
        elif graph[rx + i][ry] == "#":
            down_red = (rx + i - 1, ry)
            break

    if withBlue:
        bluehole=True
        if not redhole:
            down_blue = down_red
            down_red = (down_red[0] - 1, down_red[1])
            if not (down_red[0], down_red[1], down_blue[0], down_blue[1]) in visited:
                visited.add((down_red[0], down_red[1], down_blue[0], down_blue[1]))
                stack.append((down_red, down_blue, cnt))
    else:
        i = 1
        while True:
            if graph[bx + i][by] == ".":
                i += 1
            elif graph[bx + i][by] == "O":
                bluehole = True
                break
            elif graph[bx + i][by] == "#":
                down_blue = (bx + i - 1, by)
                break
        if redhole and not bluehole:
            break
        if not bluehole:
            if down_red[0] == down_blue[0] and down_red[1] == down_blue[1]:
                down_blue = (down_blue[0] - 1, down_blue[1])
            if not (down_red[0], down_red[1], down_blue[0], down_blue[1]) in visited:
                visited.add((down_red[0], down_red[1], down_blue[0], down_blue[1]))
                stack.append((down_red, down_blue, cnt))


if redhole:
    if bluehole:
        print(0)
    else:
        print(1)
else:
    print(0)