09_구슬게임

이 문제는 꼭 해보고싶어서 시간이 좀 걸리긴 했는데 기어코 해결을 하고야 말았다.

 

중간에 정말 왜안되는지 모르겠는 이유가 발생했는데 알고보니 파이썬에서 리스트의 복사를 하면 기본적으로 얕은복사가 되는 것이었다. 이걸 발견하기까지 정말 많이 걸렸다... 하나하나 프린트를 찍어보면서 깨닫고 아! 라고 했다..

 

from collections import deque
from copy import deepcopy

map = [
    ["#", "#", "#", "#", "#", "#", "#"],
    ["#", ".", ".", ".", "#", "B", "#"],
    ["#", ".", "#", "#", "#", "#", "#"],
    ["#", ".", ".", "R", ".", ".", "#"],
    ["#", "#", "#", "#", "#", ".", "#"],
    ["#", "O", ".", ".", ".", ".", "#"],
    ["#", "#", "#", "#", "#", "#", "#"]

]

dr = [0,1,0,-1]
dc = [-1,0,1,0]




def is_available_to_take_out_only_red_marble(game_map):


    d = 0
    count = 0
    for i in range(len(game_map)):
        if "R" in game_map[i]:
            red_r = i
            red_c = game_map[i].index("R")
        if "B" in game_map[i]:
            blue_r = i
            blue_c = game_map[i].index("B")

    queue = deque()
    queue.append((red_r, red_c, blue_r, blue_c,game_map))
    
    full_count = 0
    for x in range(10):
        full_count += 4**x


    while count <=full_count:
        red_r, red_c, blue_r, blue_c, present_game_map = queue.popleft()
        for j in range(4):
            new_game_map = deepcopy(present_game_map)
            # print('present_game_map')
            #
            # for x in range(len(present_game_map)):
            #     print(present_game_map[x])
            # print('----------------------')

            for i in range(len(game_map)):
                if "R" in present_game_map[i]:
                    red_r = i
                    red_c = present_game_map[i].index("R")
                if "B" in present_game_map[i]:
                    blue_r = i
                    blue_c = present_game_map[i].index("B")


            new_red_r = red_r + dr[j]
            new_red_c = red_c + dc[j]
            new_blue_r = blue_r + dr[j]
            new_blue_c = blue_c + dc[j]


            if present_game_map[new_red_r][new_red_c] == "O":
                return True
            elif present_game_map[new_red_r][new_red_c] == "#":
                new_red_r, new_red_c = red_r, red_c
            elif present_game_map[new_red_r][new_red_c] == "B" and present_game_map[new_red_r +dr[j]][new_red_c +dc[j]] != ".":
                new_red_r, new_red_c = red_r, red_c


            if present_game_map[new_blue_r][new_blue_c] == "O":
                new_blue_r, new_blue_c = blue_r, blue_c
            elif present_game_map[new_blue_r][new_blue_c] == "#":
                new_blue_r, new_blue_c = blue_r, blue_c


            elif present_game_map[new_blue_r][new_blue_c] == "R" and present_game_map[new_blue_r+dr[j]][new_blue_c+dc[j]] != ".":
                new_blue_r, new_blue_c = blue_r, blue_c


            new_game_map[red_r][red_c] ,new_game_map[new_red_r][new_red_c] = new_game_map[new_red_r][new_red_c],new_game_map[red_r][red_c]
            new_game_map[blue_r][blue_c], new_game_map[new_blue_r][new_blue_c] = new_game_map[new_blue_r][new_blue_c],new_game_map[blue_r][blue_c]


            if new_game_map[new_blue_r][new_blue_c] != "O" :
                queue.append((new_red_r,new_red_c,new_blue_r,new_blue_c,new_game_map))


            # print('new_game_map')
            # for x in range(len(present_game_map)):
            #     print(new_game_map[x])
            # print('----------------------')
        count +=1


    return False


print(is_available_to_take_out_only_red_marble(map))  # True 를 반환해야 합니다

중간중간 보면 원인을 찾으려고 열심히 print찍어본 흔적들이 나온다... 

 

그리고 중간에 깨달은 큰 실수(?)라고 해야하는 게 있었는데 for문을 1단계 2단계 이렇게 10단계까지 봐야하는데 나는 큐의 구조에 계속 때려넣어서 for문을 반복하는 스타일로 만들어서 count를 계산하기가 매우 복잡했다. 이걸 손보려고하면 구조적으로 아예 손봐야할것 같아서 full_count라는 변수를 만들어 그안에 직접 수식적으로 카운트를 계산해서 넣은 ㅋㅋㅋ 기염을 토했다. 이런 꽤 고난도 문제를 도움없이 직접 풀어본것만으로 엄청 뿌듯하였다.