백준 - 구슬 탈출 1, 2, 4

13459번: 구슬 탈출

13460번: 구슬 탈출 2

15653번: 구슬 탈출 4

문제

빨간 구슬을 상하좌우로 중력에 따라 기울여서 구멍 안으로 넣을 수 있는지, 넣을 수 있다면 최소 몇 번을 움직여야 하는 지 구하는 문제 입니다. 단 파란 구슬이 구멍 안으로 들어가면 안됩니다. 1,2,4 세문제 다 하나의 솔루션 코드로 풀 수 있습니다. (3번은 경로까지 찾는 문제인데 귀찮아서 안풀었어요 ㅠ). 시키는 대로 하면 되는 문제이지만, 하나하나 신경 써야 하는 구현 폭탄 문제 이기도 합니다.

접근

사용 할 알고리즘

얼핏 보면 미로 찾기 + 최소 비용 문제로 볼 수 있습니다. 최소 횟수를 구하는 문제이므로 BFS + 우선순위 큐를 이용해서 풀 수 있는데, 횟수를 기준으로 하는 우선순위 큐(최소 힙)를 사용하면 빨간 구슬이 조건에 맞춰 구멍에 도달하는 경로를 찾게 되면, 이때가 최소 횟수가 되므로 추가적인 작업 없이 바로 반복문에서 빠져나와서 정답을 출력하면 됩니다. 따라서 우선수위 큐를 사용하면 바로 정답을 출력할 수 있고, 시간 초과를 면할 수 있습니다.

케이스

상/하/좌/우 로 벽, 또는 구멍에 도달할 때 까지 구슬을 이동시켜야 하는데, 여기서 여러 케이스가 발생합니다. 빨강, 파랑이 수직 또는 수평에 있는 경우를 고려해야 합니다.

빨강/파랑이 수평에 있고 왼쪽으로 이동할 경우

예를 들어 수평으로 위치해 있는 경우, 위/아래 이동은 문제가 없지만, 좌/우 이동을 순차적으로 해야 하는 데, 왼쪽으로 이동할 때, 가장 왼쪽에 있는 구슬부터 이동한 다음, 오른쪽에 있는 구슬이 이동해야 합니다. 오른쪽에 있는 구슬은 중간에 벽 또는 구멍에 도달하거나, 빨간 구슬 위치에 도달할 때 까지 이동해야 합니다. 오른쪽도 마찬가지로 가장 오른쪽에 있는 구슬이 이동하고, 그 다음 왼쪽에 있는 구슬이 나중에 이동해야 합니다. 빨강/파랑이 수직으로 위치하고 위/아래로 움직일 경우도 유사한 방법으로 이동시키면 됩니다.

방문여부

여기서 시간을 많이 까먹었는데, 일반적인 그래프 문제와는 다르게, 빨간 구슬과 파란 구슬 두 개의 위치 방문 여부를 관리해야 합니다. 이 때 visited 객체를 빨간 구슬 파란 구슬 따로 선언하는 것이 아닌 하나의 객체로 관리해야 합니다. 왜냐하면 빨간 구슬 위치와 파란 구슬 위치의 방문 여부를 따로 선언하게 된다면 방문 하지 않은 상태에서도 방문을 했다는 것으로 판단합니다.

 

예를 들어 [빨강 구슬의 위치, 파란 구슬의 위치]라고 할 때 [1, 0] -> [0, 1] -> [1, 1]로 움직였다고 가정할 때(쉬운 이해를 위해 1차원 좌표로 설명하지만 개념은 2차원과 동일합니다.) 이 [1, 1] 위치는 처음 접근하는 위치이지만 이미 빨강, 파랑 각각 1에 한 번 씩 방문했기 때문에 [1,1]을 접근하지 않게 됩니다. 이렇게 되면 접근 할 수 있는 부분도 접근을 하지 않게 되어 성공을 할 수 있음에도 실패로 처리하게 됩니다. 반례는 아래와 같습니다.

7 9
#########
#..####.#
##.##R.##
##.###..#
###.##B##
#O......#
#########

ans:5
output:-1

그렇기 때문에 빨강위치와 파랑 위치를 하나의 객체에 관리해야 하며, visited[빨강x][빨강y][파랑x][파랑y]로 4차원 리스트로 관리하거나, 해싱을 이용해 1차원 리스트에 관리해야 합니다. 저 같은 경우 후자의 방법을 사용했습니다.

# xx xx xx xx
# red_y, red_x, blue_y, blue_x

# 예를 들어 빨강 위치가(3, 5), 파랑 위치가 (4, 7)이면 해시값은
# 05030704가 된다.

visited = [False] * 10101011
def hash_visited(r, b):
    return b[0] + b[1] * 100 + r[0] * (100**2) + r[1] * (100**3)

후기

다른 사람들에 비해서 시간이 좀 더 오래 걸렸는데, 아마 visited의 요소 갯수가 너무 많다 보니 초기화 하는 데 시간이 많이 걸린 것 같습니다.

 

코드는 너무 길어 여기에 올리지 않고 따로 깃허브에 올려두었습니다.
보기