[Programmers/python] 340211: [PCCP 기출문제] 3번 / 충돌위험 찾기

문제

✔️ Lv. 2

문제 흐름

이런 알고리즘은 뭘까?
감이 잘 안잡혔다.
잘 모르는 사람의 눈에서는 시뮬레이션?(아직 모름) 아니면 브루트포스? 같이 느껴졌다.
정말 주어진 조건에서 시키는 대로 진행되도록 했다.
코드를 보다시피 조건문이 엄청 많고 체크도 굉장히 많이 한다.
주석을 잔뜩 달아놔서 이해에 큰 어려움은 없을 거라고 생각된다.
아마..?
중간 결과를 확인할 수 있도록 중간중간 print 찍었는데 주석을 풀고 실행시켜보면 좀더 직관적으로 이해가 될 것이다.
정말 시킨대로 구현된 상태라.. 시간초과가 나지 않은게 신기하다.

idx는 x번째 로봇이 몇번째 이동을 해야하는지 저장한다.
position는 x번째 로봇의 위치를 저장한다.
complete는 x번째 로봇의 운송 완료 여부를 확인한다.
모든 로봇이 운송을 완료했다면 (=complete의 합이 로봇의 수라면) 반복문을 멈추도록 했다.

코드

def solution(points, routes):
    answer = 0
    n = len(routes) # 로봇의 수
    l = len(routes[0]) # 운송경로 길이
    idx = [0 for _ in range(n)]
    position = [[0, 0] for _ in range(n)]
    complete = [0 for _ in range(n)]

    while 1:
        pos_check = set()
        conflict = set()
        if sum(complete) == n:
            break
        for robot in range(n):
            i = idx[robot]
            # i == 0 이면 초기 위치 설정
            if i == 0:
                position[robot][0] = points[routes[robot][0]-1][0]
                position[robot][1] = points[routes[robot][0]-1][1]
#                print(f"robot_{robot}: 초기 위치 설정 {position[robot]}")
            # i == l 이면 운송 완료
            elif i == l:
                complete[robot] = 1
                idx[robot] += 1
#                print(f"robot_{robot}: 운송 완료")
                continue
            elif i > l:
                continue
                
            destination = points[routes[robot][i]-1]
            # 로봇 이동
            if position[robot][0] != destination[0]:
                move = 1 if position[robot][0] < destination[0] else -1
                position[robot][0] += move
#                print(f"robot_{robot}: 이동 {position[robot]} (destination: {destination})")
            elif position[robot][1] != destination[1]:
                move = 1 if position[robot][1] < destination[1] else -1
                position[robot][1] += move
#                print(f"robot_{robot}: 이동 {position[robot]} (destination: {destination})")
            # 목적지에 도달한 경우
            if position[robot] == destination:
                idx[robot] += 1
#                print(f"robot_{robot}: 목적지{i} 도달")

            # 충돌 여부 확인
            x, y = position[robot]
            if complete[robot]:
                continue
            if (x, y) in pos_check:
                conflict.add((x,y))
            else:
                pos_check.add((x,y))

        answer += len(conflict)
#        print(f"answer: {answer}")
    return answer

마무리

풀다 말았다고 생각했었는데 풀고 정리를 안한 문제가 있었다.
코드처럼 모든 경우의 수에 대해서 작성하느라 오래 걸렸던 걸로 기억하는데, 나같이 비효율적으로 짠다고 가정하면 문제 자체는 엄청나게 어렵진 않았던 것 같다.
다른분들 코드를 읽어봐야겠다.