[프로그래머스] Lv.2 충돌위험 방지 (파이썬)

구현, 시뮬레이션 문제

https://school.programmers.co.kr/learn/courses/30/lessons/340211

프로그래머스

---

문제 설명 

• routes = []에 몇번 point가 몇번 point로 이동할 것인지의 정보가 주어진다.
• 우리는 routes의 정보를 가지고, point -> point로 이동할 때 최단 경로만을 사용해서 이동하고 싶다.
• 이때, r좌표의 이동을 c좌표의 이동보다 우선시한다.
• 최종적으로는 routes에 있는 point -> point로 동시에 이동시킬 때, 몇 번 충돌하는지 알고 싶다.

---

접근 방식

초기

BFS를 통해 각각의 point에서 목표 point로 이동하는 최단경로를 싹 구한다.

이때, BFS를 돌리는 과정에서 queue에 이동한 현재 좌표를 리스트에 추가함으로써 이동 경로를 기록한다.

BFS를 다 돌린 후에는 zip, Counter를 활용해 i번째 초에서 각각 몇번 겹쳤는지를 기록한다.

변경 후

BFS를 돌릴 필요가 없다 !!!

(우리는 보통 그래프에서 벽으로 막혀져있거나, 지나갈 수 없는 한계상황을 피해 최단경로를 구하기 위해 BFS를 사용했다.)

 

그 이유는 좌표 -> 좌표로 이동하는 최단경로를 구하는 것이므로, 단순히 while문만 돌려주면 된다.

또, 굳이 4방향을 돌면서 BFS의 queue에 다음 좌표를 추가해줄 필요 없이, 현재 좌표에서 목표 좌표로 가기 위한 중간 좌표값만 기록해주면 된다. (r, c 우선순위도 정해져있음)

---

✏️ 짚고 넘어갈 Point

1. BFS에서 지나온 경로 기록하기

while queue:
	if (nx, ny) not in visited:
    	   queue.append((nx, ny, path + [(x, y)]))

2. zip, zip_longest

for pair in zip_longest(*pairs, fillvalue=None):

• fillvalue를 사용하면 비교할 리스트의 길이가 짧을 경우, 해당 요소를 원하는 값으로 채울 수 있다.
• *pairs는 pairs(이중 리스트)에 들어간 리스트들을 비교하기 위해 *를 사용했다.

 

사용 예시

import itertools

students = ['한민서', '황지민', '이영철', '이광수', '김승민']
rewards = ['사탕', '초컬릿', '젤리']

result = itertools.zip_longest(students, rewards, fillvalue='None')
print(list(result))

'''
출력 결과:
[('한민서', '사탕'), 
('황지민', '초콜릿'), 
('이영철', '젤리'), 
('이광수', 'None'), 
('김승민', 'None')]
'''

3. Counter 모듈 사용

cnt = Counter(filtered_pair)

for k, v in cnt.items():
	...

 

counter에서 각각의 key와 value에 접근하기 위해선 items()를 사용하면 된다.

 

사용 예시

Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})

---

💡 풀이코드 (시간초과 - BFS)

from collections import deque, Counter
from itertools import zip_longest

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

pairs = []

def solution(points, routes):
    answer = 0

    def bfs(startX, startY, targetX, targetY, path):
        queue = deque()
        queue.append((startX, startY, path))
        visited = set()
        visited.add((startX, startY))
        
        while queue:
            x, y, path = queue.popleft()
            
            # new_path = path + [(x, y)]  
            
            if x == targetX and y == targetY:
                return path
            
            for ii in range(4):
                ny = dy[ii] + y
                nx = dx[ii] + x
                
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, path + [(x, y)]))
        return [] 

    for r in routes:
        j = deque(r)
        
        path = []
        
        while len(j) >= 2:
            s = j.popleft()
            n = j[0]
            
            startX = points[s-1][0]-1
            startY = points[s-1][1]-1
           
            targetX = points[n-1][0]-1
            targetY = points[n-1][1]-1

            path = bfs(startX, startY, targetX, targetY, path)       
            
        path = path + [(points[j[0]-1][0]-1, points[j[0]-1][1]-1)]
            
        if path:  
            pairs.append(path)
    

    for pair in zip_longest(*pairs, fillvalue=None):
        filtered_pair = [p for p in pair if p is not None] 
        cnt = Counter(filtered_pair)

        for k, v in cnt.items():
            if v > 1:
                answer += 1

    return answer

 

시간 복잡도

1. bfs 함수의 시간 복잡도

bfs(startX, startY, targetX, targetY, path)

• BFS의 최악의 경우는 2차원 격자(100x100)에서 모든 칸을 탐색하는 경우이다.
• 최악의 경우 O(R x C) = O(100 x 100) = O(10000)
• 하지만 BFS는 시작점에서 최단 거리만 탐색하므로, 평균적으로 O(D) (목표 지점까지의 거리) 정도만 탐색된다.
• 최악의 경우, D는 격자의 크기만큼(100) 될 수 있어 O(100) = O(10²).

2. bfs 함수 호출 횟수

routes의 최대 길이 = 100

routes[i]의 최대 길이 = 100

for r in routes:
    j = deque(r)

    while len(j) >= 2:
        ...
        path = bfs(startX, startY, targetX, targetY, path)

 

총합 = O(100 ~ 10000) X O(100) X O(100) = O(1000000) ~ O(100000000)

 

즉, BFS 함수의 시간 복잡도에 따라 최소 백만번 ~ 억번 실행될 수 있다. -> 시간 초과 

 

고친 코드

routes = [[2, 3, 4, 5], [1, 3, 4, 5]]처럼 시작점이 끝점까지 도달하는 과정에서 거쳐야 하는 점들이 여러 개 있는 경우도 있다.

위의 예로 들면 2번 point에서 5번 point로 도달하는 과정에서 3번 point와 4번 point도 거쳐가야 하는 것이다.

 

이를 위해 처음에는 아래와 같이 구현했다.

하지만, 아래처럼 구현할 경우에는 시작점(2)에서 끝점(5)로 가는 최단 경로를 구해버린다. 

(혹은 시작점(2)에서 중간점(3) / 중간점(4)로 각각 가는 최단 경로를 구해버린다.)

시작점(2)에서 중간점(3, 4)를 거쳐  끝점(5)로 가는 경로가 아니다.

if x == points[tarList[0]-1][0]-1 and y == points[tarList[0]-1][1]-1:
    print(tarList, points[tarList[0]-1][0]-1, points[tarList[0]-1][0]-1)
    tarList.pop(0)
    print(new_path)
    if len(tarList) == 0:
        return new_path  # 최단 경로 반환

---

💡 풀이코드 (성공- 시뮬레이션)

# bfs 돌릴 필요가 없음 (장애물이 있는 것도 아니고, 최단 거리만 찾으면 됨 (r, c) 조건에 따라 )

from collections import deque, Counter
from itertools import zip_longest

pairs = []

def solution(points, routes):
    answer = 0

    def sol(startX, startY, targetX, targetY, path):
    
        while startX != targetX:
            if startX < targetX:
                startX += 1
            else:
                startX -= 1
            path.append((startX, startY))
        
            
        while startY != targetY:
            if startY < targetY:
                startY += 1
            else:
                startY -= 1
            path.append((startX, startY))
        
        return path 

    for r in routes:
        j = deque(r)
        
        path = []
        path = path + [(points[j[0]-1][0]-1, points[j[0]-1][1]-1)]
        
        while len(j) >= 2:
            s = j.popleft()
            n = j[0]
            
            startX = points[s-1][0]-1
            startY = points[s-1][1]-1
            
            targetX = points[n-1][0]-1
            targetY = points[n-1][1]-1

            path = sol(startX, startY, targetX, targetY, path)
            
        pairs.append(path)
    
    for pair in zip_longest(*pairs, fillvalue=None):
        cnt = Counter(pair)

        for k, v in cnt.items():
            if v > 1 and k != None:
                answer += 1

    return answer

 

주요 로직

• 현재 x좌표와 목표 x좌표를 비교해서 x좌표가 가까워질수 있도록 좌표값을 1씩 증가 / 감소해준다.
  그리고, 이동 경로를 기록하기 위해 현재 x좌표와 y좌표를 path 리스트에 추가해준다.
• 현재 y좌표와 목표 y좌표를 비교해서 y좌표가 가까워질수 있도록 좌표값을 1씩 증가 / 감소해준다.
  그리고, 이동 경로를 기록하기 위해 현재 x좌표와 y좌표를 path 리스트에 추가해준다.

while startX != targetX:
    if startX < targetX:
        startX += 1
    else:
        startX -= 1
    path.append((startX, startY))


while startY != targetY:
    if startY < targetY:
        startY += 1
    else:
        startY -= 1
    path.append((startX, startY))

---

* 참고문헌

https://windy7271.tistory.com/entry/PythonLV2-PCCP-%EA%B8%B0%EC%B6%9C%EB%AC%B8%EC%A0%9C-3%EB%B2%88-%EC%B6%A9%EB%8F%8C%EC%9C%84%ED%97%98-%EC%B0%BE%EA%B8%B0

(Python/LV2) [PCCP 기출문제] 3번 / 충돌위험 찾기