백준 구슬탈출2 파이썬

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

import sys
from collections import deque

sys.setrecursionlimit(10000)

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().rstrip().split())

    ball_start_pos = {}
    graph = []
    for i in range(N):
        data = sys.stdin.readline().rstrip()
        r_i = data.find('R')
        b_i = data.find('B')
        if r_i != -1:
            ball_start_pos['R'] = (i, r_i)
        if b_i != -1:
            ball_start_pos['B'] = (i, b_i)
        graph.append(list(data))

    visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]


    def tilt_graph(v, h, direction):
        count = 0
        while graph[v + direction[0]][h + direction[1]] != '#' and graph[v][h] != 'O':
            v += direction[0]
            h += direction[1]
            count += 1

        return v, h, count


    def bfs():
        # 빨간공, 파란공의 시작지점 큐 삽입
        q = deque([(ball_start_pos['R'][0], ball_start_pos['R'][1], ball_start_pos['B'][0], ball_start_pos['B'][1], 1)])

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while q:
            rv, rh, bv, bh, move_cnt = q.popleft()
            if move_cnt > 10:
                print(-1)
                return
            for d in directions:
                nrv, nrh, rcnt = tilt_graph(rv, rh, d)
                nbv, nbh, bcnt = tilt_graph(bv, bh, d)

                # 파란공이 구멍에 빠질 경우
                if graph[nbv][nbh] == 'O':
                    continue

                # 빨간공이 구멍에 빠질 경우
                if graph[nrv][nrh] == 'O':
                    print(move_cnt)
                    return

                # 공의 위치가 같은곳이라면 공의 위치 조정 (공이 같은위치에 있을 수는 없음)
                if nrv == nbv and nrh == nbh:
                    # 빨간공과 파란공 중 이동횟수가 더 많은 공을 한 칸 이전으로 이동 (공이 더 많이 이동했다는 것은 진행방향보다 한칸더 이전에 있었다는 것이기 때문)
                    if rcnt > bcnt:
                        nrv -= d[0]
                        nrh -= d[1]
                    else:
                        nbv -= d[0]
                        nbh -= d[1]

                if not visited[nrv][nrh][nbv][nbh]:
                    visited[nrv][nrh][nbv][nbh] = True
                    q.append((nrv, nrh, nbv, nbh, move_cnt + 1))
        print(-1)
bfs()

 

와 .. 이거 오지게 어려웠다.

혼자 이래저래 구현해보다가 빨간공과 파란공 이동을 모두 고려해야하는 부분에서 구현이 많이꼬여서 결국 다른분 코드를 참고해서 풀었다.

이 문제의 핵심아이디어는

방문 기록을 위해 4차원 배열을 쓰는것과 한번 이동할때 더이상 이동할 수 없을때까지 이동하는것.

그리고 두개의 구슬을 모두 이동시킨후 같은 지점에서 만난 경우 움직인 횟수를 비교하여 더 많이 움직인 구슬을 한칸 이전으로 되돌리는것이다.

더 많이 움직인 구슬을 한칸 이전으로 되돌리는 이유는 

예를들어 # 길 길 길 (빨) (파) 라고 했을 때, 

빨간 구슬, 파란구슬을 모두 벽이 만날때까지 이동시키면 왼쪽 끝 마지막 길까지 갈것이다. 헌데 파란 구슬이 빨간 구슬 보다 뒤에 있으므로

똑같이 마지막 길까지 갔을때 파란 구슬이 빨간구슬보다 이동횟수가 1 더 많을 것이고 구슬은 겹쳐질수 없으므로 이동횟수가 많은 파란공을  한칸 이전으로 되돌리는 것이다.

내 구현능력이 아직 형편없다고 느꼈다.. 

더 분발하자.