🚚 운송 로봇 충돌 문제 — 해결 여정 정리

이 문서는 첫 번째 구현부터 최종 정답까지 어떤 이유로 오답이 발생했고,
어떤 식으로 문제를 해결해 갔는지를 단계별로 정리한 기록이다.

1. ✅ 첫 번째 구현의 설계 방식

초기 구현의 핵심 논리는 다음과 같았다.

✔ 구현 아이디어

1. 각 로봇이 이동하는 모든 지점을 movebot()으로 계산해 리스트에 담는다.

2. zip_longest(*paths)로 시간 t에 로봇들이 있는 좌표를 동시에 비교한다.

3. 시간이 같고 좌표가 같은 경우 충돌 카운트 증가.

✔ movebot()이 생성하는 데이터 형태

출발점 → 도착점까지 X → Y 순으로 이동 경로 좌표를 차례대로 리스트로 구성.

2. ❌ 초기 구현이 틀렸던 이유

실제로 제출하면 몇몇 케이스에서만 오답이 나왔다.
주요 원인을 정리하면 다음과 같다.

문제 1. 로봇별 “전체 시간 경로”가 아니라 “구간별 경로”를 저장함

초기 코드:

moveArr.append(r)

여기서 moveArr는 다음 형태가 됨:

[ r1_구간1, r1_구간2, r2_구간1, r3_구간1, ... ]

즉,

• 로봇 1의 전체 경로가 아니라

• 로봇 1의 구간별 경로가 따로따로 저장되고

• 로봇 2, 로봇 3의 구간 경로가 섞여 들어감

그다음 zip_longest(*moveArr)을 돌리면:

t=0 → r1_구간1[0], r1_구간2[0], r2_구간1[0], ...
t=1 → r1_구간1[1], r1_구간2[1], ...

즉, 시간축 자체가 깨짐
전혀 다른 시간의 좌표들을 "같은 시간"처럼 비교하게 되어 충돌 계산이 틀어짐.

문제 2. 충돌 횟수 계산 방식 오류

초기 구현:

if strx[str(y)] > 1:
    result += 1

이 방식은 아래처럼 잘못된 값을 만든다.

• 같은 시각 같은 좌표에 로봇 3대가 모이면
  → count = 1, 2, 3
  → 2일 때 +1
  → 3일 때 또 +1
  → 실제로는 1회여야 하는데 2회 증가

즉, 중복 충돌이 과다 계산됨.

정답 규칙은

하나의 좌표에 두 대 이상 모이면 '1'번만 증가한다.

따라서 “1 → 2”가 되는 순간만 세야 한다.

문제 3. 출발 시점(t=0) 충돌 누락

문제에서는:

로봇은 모두 0초에 동시에 출발한다.
출발 좌표도 충돌 가능성이 있음.

하지만 초기 구현에서는 t=0의 출발 좌표를 날짜에 넣지 않아서
시작점에서 로봇들이 같은 포인트에 있을 경우의 충돌을 누락했다.

문제 4. movebot()의 이동 경로 계산 오류

초기의 movebot에서는 다음 문제가 있었다.

• X축 이동 + Y축 이동 순서가 불안정하게 갱신됨

• 업데이트된 x,y를 유지하지 않고 잘못된 좌표를 찍는 케이스가 있었음
  (특정 테스트에서 불일치 → 충돌이 누락됨)

3. 🔧 주요 수정 단계

3-1. 로봇별 전체 경로 배열 생성

기존: moveArr = [구간1, 구간2, ...]
→ 변경: paths = [로봇1_전체경로, 로봇2_전체경로, ...]

이렇게 모든 로봇의 경로를 하나로 이어붙여서 정확한 시간 축을 맞춤.

3-2. t=0 출발 좌표 포함

x0, y0 = points[start - 1]
path.append((x0, y0))

이제 출발 순간 충돌까지 모두 계산됨.

3-3. 충돌 카운트 방식 보정

잘못된 방식:

if count > 1:
    result += 1

올바른 방식:

if count == 2:
    result += 1

즉, "1 → 2"로 증가할 때만 1회 카운트.

3-4. movebot() 올바르게 재구현

다음 규칙을 정확히 반영:

• r(x) 먼저 이동

• 그다음 c(y) 이동

• 이동할 때마다 한 칸씩 path 기록

4. 🎯 최종 정답 코드

아래는 모든 오류를 고쳐 완성된 정답 코드.

from itertools import zip_longest
 
def movebot(x1, y1, x2, y2):
    path = []
    x, y = x1, y1
    
    # r 좌표(x) 먼저 이동
    if x1 != x2:
        d = 1 if x2 > x1 else -1
        for nx in range(x1 + d, x2 + d, d):
            x = nx
            path.append((x, y))
    
    # 그 다음 c 좌표(y) 이동
    if y1 != y2:
        d = 1 if y2 > y1 else -1
        for ny in range(y1 + d, y2 + d, d):
            y = ny
            path.append((x, y))
    
    return path
 
 
def solution(points, routes):
    paths = []
    
    for route in routes:
        path = []
        
        start = route[0]
        x0, y0 = points[start - 1]
        path.append((x0, y0))
        
        for i in range(len(route) - 1):
            s = route[i]
            e = route[i + 1]
            x1, y1 = points[s - 1]
            x2, y2 = points[e - 1]
            
            seg = movebot(x1, y1, x2, y2)
            path.extend(seg)
        
        paths.append(path)
    
    result = 0
    
    for step in zip_longest(*paths, fillvalue=None):
        counter = {}
        for pos in step:
            if pos is None:
                continue
            if pos in counter:
                counter[pos] += 1
                if counter[pos] == 2:
                    result += 1
            else:
                counter[pos] = 1
    
    return result

5. 🎉 요약 – 최종 완성까지의 핵심 변화