05_catchme 문제! ( 상반기 line인턴채용문제)

 

처음에 문제를 딱 보고 들었던 생각은 우선 코니의 위치를 생각한 다음에 브라운의 위치를 이전에 배운 BFS방식으로 쭉 나열해서 대입하면 되지 않을까??! 라는 생각이었다.

 

결론적으로 접근방식이 맞긴 했는데 구현하지는 못했다. 나는 시간에 따라서 위치를 어떻게 이중배열로 해야하나.. 고민하고 있었는게 고민하다 안풀려서 강사님의 해결답안을 보았는데 딕셔너리를 이용하여 푸셨다!

 

from collections import deque

c = 11
b = 2
queue = deque()

def catch_me(cony_loc, brown_loc):
    # 구현해보세요!
    time = 0
    queue = deque()
    queue.append((brown_loc,0))
    visited = [{} for _ in range(201)]

    while cony_loc < 200000:
        cony_loc += time
        print(cony_loc)
        if time in visited[cony_loc]:
            print(cony_loc)
            return time

        for i in range(0,len(queue)):
            current_position, current_time = queue.popleft()

            new_time = current_time+1
            new_position = current_position - 1
            if 0 <= new_position <= 200000:
                queue.append((new_position,new_time))
                visited[new_position][new_time] = True
            new_position = current_position + 1
            if 0 <= new_position <= 200000:
                queue.append((new_position, new_time))
                visited[new_position][new_time] = True
            new_position = current_position * 2
            if 0 <= new_position <= 200000:
                queue.append((new_position, new_time))
                visited[new_position][new_time] = True

        print(visited[25])
        time +=1





print(catch_me(c, b))  # 5가 나와야 합니다!

코니의 위치를 while문의 변수로 삼은 후에, visited라는 리스트를 통해 미리 201개의 리스트를 만들어 두었다.

위 코드에선 201개지만 실제로 다른예시까지 수용하려면 200001 개의 리스트를 미리 만들어내야한다! 코드 중간중간의 print들은 코드 이해를 위해 넣었던거라 무시하고 보면 된다.

 

아무튼 이러면 visited리스트안에 [ [] , [], [],[] ...] 이렇게 많이 되어있을테고 코니의 시간에 따른 브라운의 개수는 3배수로 계속 늘어나기에 BFS를 쓴다는 생각이 들었다.

 

그래서 1초가 지난 후에는 위치할수 있는 브라운의 위치가 1,3, 4 이므로 1초가 지난후의 visited 리스트안에는

[ [ 1 : true ] , [], [ 1 : true], [1 : true] , ... ] 이런식으로 위치에 따른 시간 좌표가 천천히 쌓일 것이다. 이러다가 time의 시간에 코니와 브라운의 위치가 겹친다면, 브라운이 잡았다고 생각할 수 있는 것이다.