[PCCP 기출문제] 3번 / 충돌위험 찾기

문제

프로그래머스

 

문제 풀이

• 우선 시작지점과 거쳐야하는 지점을 구한다.
• 증가하는 시간을 인덱스로 두고 이동하는 좌표들을 dict에 모두 저장한다.
• 이 때 r좌표의 이동을 c좌표보다 우선한다는 조건에 따라 사방탐색이 아닌 [r, c]의 값을 따로 이동시켜야하는 것이 핵심이다.
• 이동을 마쳤다면 dict에서 같은 시간에 같은 경로를 방문한 케이스가 있는지 확인하여 있다면, answer을 증가시킨다.

---

defaultdict

✅ 일반 딕셔너리는 key가 없을 때 오류가 나지만, defaultdict는 key가 없으면 자동으로 기본값을 만들어준다.

→ key가 없는데도 path[1]에 바로 .append() 할 수 있다.

from collections import defaultdict

path = defaultdict(list)

path[0].append((1, 2))
path[0].append((3, 4))
path[1].append((1, 2))

print(path)
# 출력: defaultdict(<class 'list'>, {0: [(1, 2), (3, 4)], 1: [(1, 2)]})

 

Counter

✅ 리스트 안에 같은 값이 몇 번 등장했는지 쉽게 셀 수 있다.

→ 문제에서는 특정 시간대에 같은 좌표가 2번 이상 등장하면 경로가 겹쳤다는 의미로 활용했다.

from collections import Counter

positions = [(1, 2), (3, 4), (1, 2), (5, 6), (3, 4)]
count = Counter(positions)

print(count)
# 출력: Counter({(1, 2): 2, (3, 4): 2, (5, 6): 1})

# 중복된 위치만 출력하고 싶다면
for pos in count:
    if count[pos] > 1:
        print(f"{pos}는 {count[pos]}번 등장")

---

코드

from collections import defaultdict, Counter
def solution(points, routes):
    answer = 0
    path = defaultdict(list)
    
    # 시작위치 확인
    for route in routes:
        time = 0
        y, x = points[route[0] - 1][0], points[route[0] - 1][1]

        # 타겟위치가 여러 곳인 경우 고려해서 확인
        for i in range(1, len(route)):
            target_y, target_x = points[route[i] - 1][0], points[route[i] - 1][1]
            
            # 가장 첫 좌표 저장
            if i == 1:
                path[time].append((y, x))
            
            # y좌표 선 이동
            while y != target_y:
                if y < target_y:
                    y += 1
                else:
                    y -= 1
                time += 1
                path[time].append((y,x))
                
            # x좌표 이동
            while x != target_x:
                if x < target_x:
                    x += 1
                else:
                    x -= 1
                time += 1
                path[time].append((y, x))
                
    
    for p in path:
        c = Counter(path[p])
        for key in c:
            if c[key] > 1:
                answer += 1
                
    return answer