[백준] 13460 구슬 탈출2 (Python 파이썬)

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

문제 설명

위의 문제의 그림처럼 N * M 의 보드가 주어졌을 때, 빨간색 구슬을 구멍안에 넣는 게임이다.

파란색 구슬이 구멍안에 들어가서도 안되고,

굴리는 횟수가 10번을 넘어가서도 안된다.

 

여러가지 제약조건들이 많은 까다로운 BFS 문제이다.

---

풀이 과정

구슬을 굴리게 되면, 벽이나 구멍에 닿을 때 까지 구슬은 계속 굴러간다.

따라서, 방향 하나를 정했을 때 그 방향으로 계속 굴러가도록 while문을 통해 구슬을 굴려준다.

(코드의 roll함수의 while 부분)

 

또, 구슬이 굴러가다가 다른색의 구슬과 마주쳤을 경우에는

앞에 있는 구슬이 멈추면 내 구슬은 그 전칸에서 멈추게 되므로

각 구슬의 카운트를 통해 어떤 구슬이 앞에 있던 구슬인지 표기를 해준 후, 순서에 맞게 구슬을 배치하도록 한다.

 

또한, 4차원 visited 배열을 통해

발생했던 상황은 또 다시 발생하지 않도록 해준다.

 

2차원이 아닌 4차원 배열을 이용한 이유는

빨간색 구슬의 좌표는 이전과 같을지라도 파란색 구슬의 좌표가 다르다면 다른 상황이기 때문이다.

 

이를 파이썬 코드로 나타내면 다음과 같다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(input()))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]


def roll(x, y, direct):
    cnt = 0

    while graph[x + dx[direct]][y + dy[direct]] != '#' and graph[x][y] != 'O':
        x += dx[direct]
        y += dy[direct]
        cnt += 1

    return x, y, cnt


def bfs(ra, rb, ba, bb):
    queue = deque()
    queue.append((ra, rb, ba, bb, 1))

    while queue:
        rx, ry, bx, by, cnt = queue.popleft()
        visited[rx][ry][bx][by] = True

        if cnt > 10:
            print(-1)
            exit(0)

        for i in range(4):
            nrx, nry, rcnt = roll(rx, ry, i)
            nbx, nby, bcnt = roll(bx, by, i)

            if graph[nbx][nby] != 'O':
                if graph[nrx][nry] == 'O':
                    print(cnt)
                    exit(0)
				
                # 겹쳤을 때, 앞 뒤를 구분하여 재배치
                if nrx == nbx and nry == nby:
                    if rcnt > bcnt:
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    queue.append((nrx, nry, nbx, nby, cnt+1))

    print(-1)
    return


rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            rx = i
            ry = j
        if graph[i][j] == 'B':
            bx = i
            by = j

bfs(rx, ry, bx, by)

 

ps. 실패 코드

이 코드는 방문했던 지점을 다시 방문하게 되면서 히든 케이스들을 통과하지 못한 코드이다.

참고용으로 첨부해놓았다.

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(input()))

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


def redBall(x, y, direct):
    nx = x + dx[direct]
    ny = y + dy[direct]
    while True:
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            break
        if graph[nx][ny] == '#':
            break
        if graph[nx][ny] == 'O':
            graph[x][y] = '.'
            return -1, -1
        if graph[nx][ny] == 'B':
            bx, by = blueBall(nx, ny, direct)
            if bx == nx and by == ny:
                graph[x][y] = '.'
                graph[nx-dx[direct]][ny - dy[direct]] = 'R'
                return nx - dx[direct], ny - dy[direct]
            if bx == -1 and by == -1:
                print(-1)
                exit(0)

        nx = nx + dx[direct]
        ny = ny + dy[direct]

    graph[x][y] = '.'
    graph[nx - dx[direct]][ny - dy[direct]] = 'R'

    return nx - dx[direct], ny - dy[direct]


def blueBall(x, y, direct):
    nx = x + dx[direct]
    ny = y + dy[direct]
    while True:
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            break
        if graph[nx][ny] == '#':
            break
        if graph[nx][ny] == 'O':
            return -1, -1
        if graph[nx][ny] == 'R':
            rx, ry = redBall(nx, ny, direct)
            if rx == nx and ry == ny:
                graph[x][y] = '.'
                graph[nx - dx[direct]][ny - dy[direct]] = 'B'
                return nx - dx[direct], ny - dy[direct]

        nx = nx + dx[direct]
        ny = ny + dy[direct]

    graph[x][y] = '.'
    graph[nx-dx[direct]][ny-dy[direct]] = 'B'

    return nx - dx[direct], ny - dy[direct]


def bfs(ra, rb, ba, bb):
    queue = deque()
    queue.append((ra, rb, ba, bb, 1))
    res = 1
    while queue:
        rx, ry, bx, by, cnt = queue.popleft()
        if cnt > 10:
            print(-1)
            exit(0)

        for i in range(4):
            nrx, nry = redBall(rx, ry, i)
            nbx, nby = blueBall(bx, by, i)
            if nrx == -1 and nry == -1:
                if nbx == -1 and nby == -1:
                    print(-1)
                    exit(0)
                else:
                    print(cnt)
                    exit(0)
            queue.append((nrx, nry, nbx, nby, cnt+1))

        res = cnt
    return res

rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            rx = i
            ry = j
        if graph[i][j] == 'B':
            bx = i
            by = j

print(bfs(rx, ry, bx, by))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !