[백준13460/골드1] 구슬 탈출 2 - Python

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

 

✅ 문제 조건

 

1. 보드 상하좌우로 욺직여서 구슬 이동
2, 빨간구슬만 빼내기
3. 각 단계마다 네방향으로 기울이며 두 구슬을 동시에 이동
3-1. 파란구슬이 구멍에 빠지면 실패
3-2. 빨간구슬이 구멍에 빠지면 성공
4. 10회 반복 후, 성공 못하면 -1

 

 

✅ 접근 방법

 

# 문제 1

먼저 상하좌우로 이동하며 그때마다 턴을 반복해야한다는 건 이해했지만, 두 개의 구슬이 같은 위치에 겹치면 어떻게 처리해야할지 생각하는 데 오래걸렸다.

그래서 구슬의 위치와 현재 방향을 바탕으로 어떤 구슬이 먼저 움직어야하는지 계산할까 생각했지만 너무 복잡해서 포기했다.

위의 방법을 고민하던 중, 어떤 구슬이 먼저 움직어야하는지 계산을 하지 말고 일단 그냥 두 개의 구슬을 똑같이 굴린 후의 위치가 같다면 둘 중 더 많은 거리를 굴러온 구슬의 위치를 한 칸 뒤로 움직이면 된다고 생각했다.

 

# 문제 2

그리고 visited 배열을 어떻게 만들지고 고민이 됐다.

파란구슬, 빨간 구슬의 위치를 서로 어디에 있는지 전부 표시를 해줘야 했기 때문에 보통 2차원 배열로는 불가능했다.

그럼 그냥 저장해야 하는 정보는 4개(빨간구슬 x,y 좌표 / 파란 구슬 x,y 좌표) 였기 때문에 4차원 배열을 만들면 됐다.

 

그리고 이걸 바탕으로 매번 구슬을 굴릴 때마다 queue에 저장해서 조건을 만족할때까지 반복했다.

 

✅ 구현

 

1. 구슬 굴리기 함수 move

def move(x, y, dx, dy, board):
    cnt = 0 # 이동 거리
	
    # (x, y)에서 시작해서 한쪽 방향(dx, dy)로 가능할 때 까지 굴리기
    while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
	
    # 최종 위치 (x, y)와 이동거리 cnt 반환
    return x, y, cnt

 

2. 구슬 네 방향으로 탐색 반복 함수 bfs

def bfs(board, rx, ry, bx, by): # 빨간구슬 위치 (rx, ry), 파란구슬 위치 (bx, by)
	
    # 방문 처리
    visited = [[[[False] * 10 for _ in range(10)] for _ in range(10)] for _ in range(10)]
    visited[rx][ry][bx][by] = True

    q = deque([(rx, ry, bx, by, 0)])

    while q:
        rx, ry, bx, by, depth = q.popleft()

        # 10번 넘게 기울이면 실패
        if depth >= 10:
            return -1
        
        # 네 방향 중 한 방향으로 이동
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:

            nrx, nry, rc = move(rx, ry, dx, dy, board) # 빨간구슬 결과
            nbx, nby, bc = move(bx, by, dx, dy, board) # 파란구슬 결과

            # 파란 구슬이 빠지면 실패
            if board[nbx][nby] == 'O':
                continue

            # 빨간 구슬 빠지면 성공
            if board[nrx][nry] == 'O':
                return depth + 1

            # 구슬이 같은 위치에 있으면, 더 많이 이동한 구슬을 한 칸 뒤로
            if (nrx, nry) == (nbx, nby):
                if rc > bc:
                    nrx -= dx
                    nry -= dy

                else:
                    nbx -= dx
                    nby -= dy

            # 아직 방문하지 않은 상태이면 큐에 추가
            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, depth + 1))

    return -1

 

3. 입력 및 구슬 위치 찾은 후 결과 출력

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':
            rx, ry = i, j
        if board[i][j] == 'B':
            bx, by = i, j

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

 

 

✅ 정답 코드

'''
1. 보드 상하좌우로 욺직여서 구슬 이동
2, 빨간구슬만 빼내기
3. 각 단계마다 네방향으로 기울이며 두 구슬을 동시에 이동
3-1. 파란구슬이 구멍에 빠지면 실패
3-2. 빨간구슬이 구멍에 빠지면 성공
3-3. 두 구슬이 같은 위치에 있으면 더 많이 이동한 쪽을 한 칸 뒤로 이동 (중요!)
4. 10회 반복 후, 성공 못하면 -1
'''

from collections import deque

# 구슬 굴리기
def move(x, y, dx, dy, board):
    cnt = 0 # 이동 거리

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

    return x, y, cnt

# 구슬 탐색
def bfs(board, rx, ry, bx, by):
    visited = [[[[False] * 10 for _ in range(10)] for _ in range(10)] for _ in range(10)]
    visited[rx][ry][bx][by] = True

    q = deque([(rx, ry, bx, by, 0)])

    while q:
        rx, ry, bx, by, depth = q.popleft()

        # 10번 넘게 기울이면 실패
        if depth >= 10:
            return -1
        
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:

            nrx, nry, rc = move(rx, ry, dx, dy, board)
            nbx, nby, bc = move(bx, by, dx, dy, board)

            # 파란 구슬이 빠지면 실패
            if board[nbx][nby] == 'O':
                continue

            # 빨간 구슬 빠지면 성공
            if board[nrx][nry] == 'O':
                return depth + 1

            # 구슬이 같은 위치에 있으면, 더 많이 이동한 구슬을 한 칸 뒤로
            if (nrx, nry) == (nbx, nby):
                if rc > bc:
                    nrx -= dx
                    nry -= dy

                else:
                    nbx -= dx
                    nby -= dy

            # 아직 방문하지 않은 상태이면 큐에 추가
            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, depth + 1))

    return -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':
            rx, ry = i, j
        if board[i][j] == 'B':
            bx, by = i, j

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

 

 

다 풀고 났더니 다른 bfs 골드 1, 2 난이도 문제보다 훨씬 간단한 거 같은데 빨간 구슬과 파란 구슬의 위치를 안겹치게 하는 처리를 어떻게 할지 거의 일주일 동안 고민한 거 같다..