[백준] 13460번: 구슬 탈출 2 - 파이썬

문제보기

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

13460번: 구슬 탈출 2

 

 

---

 

풀이 & 코드

해당 문제는 알고리즘 문제를 풀다보면 흔하게 볼 수 있는 2차원 배열과 bfs를 이용하는 문제로 관련된 문제들을 좀 풀어봤다면 시간은 좀 걸려도 충분히 풀 수 있는 문제이다. 만일 풀어본 적이 없거나 풀지 못했다면 부족한 점을 채울 수 있는 좋은 기회가 될 것이다.

 

기존 문제들과 다른 특별한 점을 뽑자면 한칸만 이동하는 것이 아닌 벽이나 구멍이 나올 때까지 계속해서 이동해야한다는 점과 이동시켜야 할 구슬이 2개로 서로 겹칠 수 없는 조건을 뽑을 수 있겠다. 필자는 while문을 이용한 move라는 함수를 만들어 특정 조건을 만족할 때까지 이동하도록 만들었고, 구슬 2개를 따로 실행한 후에 겹쳤을 경우 더 많이 이동한 것을 뒤로 반대방향으로 이동시키는 방법으로 조건들을 만족시켜 주었다.

 

 

---

 

먼저 move(x, y, d) 함수이다. 파라미터 d로 설정된 방향대로 while을 돌면서 칸을 이동하며, 현재 칸이 벽이라면 이전 칸을 반환하고 현재 칸이 구멍이라면 현재 칸을 리턴하도록 구성하였다.

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

def move(x, y, d):
    while True:
        nx, ny = x + dx[d], y + dy[d]
        if board[ny][nx] == "#":
            return x, y
        if board[ny][nx] == "O":
            return nx, ny
        
        x, y = nx, ny

 

 

두 번째로 move함수를 통해 이동한 두 구슬이 겹쳤을 경우, 이동거리를 계산해 이동한 거리가 많은 구슬을 뒤로 한 칸 이동시켜주었다. 이동거리는 절댓값 메서드인 abs()를 사용하여 계산하였다.

if (nby, nbx) == (nry, nrx):
    r_move = abs(nrx + nry - rx - ry)
    b_move = abs(nbx + nby - bx - by)
    if r_move > b_move:
        nrx, nry = nrx - dx[d], nry - dy[d]
    else:
        nbx, nby = nbx - dx[d], nby - dy[d]

 

 

마지막으로 실행 시간을 줄이기 위해 visited라는 4차원 리스트를 만들어 만일 두 구슬의 위치가 이전에 나온적 없는 경우에만 deq에 추가하도록 조건문을 작성하였고, 10번 이하로만 움직일 수 있어 depth가 10이상인 경우도 deq에 추가시켜주지 않았다.

if visited[nrx][nry][nbx][nby] == 0 and depth < 10:
    visited[nrx][nry][nbx][nby] = 1
    deq.append([depth+1, nrx, nry, nbx, nby])

 

참고로 다른 분들은 4차원 배열이 아닌 일차원 배열에 길이가 4인 배열을 추가하는 방향으로 작성하신 분들도 많다. 필자가 돌려본 결과 실행 시간은 비슷했지만 후자의 방법이 더 짧았다. 아무래도 4차원 배열이다 보니 사이즈가 커졌기 때문에 일차원을 이용한 방식이 더 유리했다고 생각된다. 후자의 방식을 사용하면 다음과 같이 작성할 수 있다.(하지만 4차원이 아니라면 차원을 늘려주는 것이 더 유리할 것으로 생각된다. 둘다 기억하고 있다가 상황에 맞게 사용하자)

visited = [[rx, ry, bx, by]]

...

if [nrx, nry, nbx, nby] not in visisted and depth < 10:
    visited.append([nrx, nry, nbx, nby])
    deq.append([depth+1, nrx, nry, nbx, nby])

 

 

---

 

전체코드