문제의 상세한 내용은 링크에서 확인할 수 있다.
https://school.programmers.co.kr/learn/challenges?order=recent&partIds=56389
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr
문제 자체는 단순하지만 문제에서 변수를 여러 개 두었기 때문에 이해하는데 호흡이 길다. 우선 문제를 간단히 하면 다음과 같다. 좌표평면 상에서 움직이고, 목적지까지 최단거리로 이동하는 로봇들이 있다. 이 로봇들은 Y축 이동을 한후 X축 이동을 하기에 이동경로가 항상 정해져 있다. 결과적으로 로봇들 간에 충돌이 일어나는 횟수를 구하는 문제이다. 이해할 수 있게 그림 예시도 있다.
편의상 1의 위치를 (3,2), 2의 위치는 (6,4), 3의 위치는 (4,7), 4의 위치는 (1,4)라고 하자.
그림처럼 로봇들이 움직일 때, 3초가 지났을 때 1번 로봇과 2번 로봇이 (4, 4)에서 충돌할 위험이 있다. 따라서 1을 return 해야 합니다. 예시를 한 개만 더 봐보자
1, 3, 4번 로봇의 경로가 같아 이동하는 0 ~ 2초 내내 충돌 위험이 존재한다. 3초에는 1, 2, 3, 4번 로봇이 모두 (4, 4)를 지나지만 위험 상황은 한 번만 발생한다. 4 ~ 5초에는 1, 3번과 2, 4번 로봇의 경로가 각각 같아 위험 상황이 매 초 2번씩 발생한다. 마지막 6초에 2, 4번 로봇의 충돌 위험이 발생한다. 따라서 9를 return 해야 합니다.
처음에는 1번 로봇이 0초, 1초, 2초에 어디인지 2번 로봇이 0초, 1초, 2초에 어디인지 2차원 배열로 저장하려 했다. 하지만 이 문제의 핵심은 충돌 횟수만 구하면 되는 것이다. 따라서 로봇마다 위치를 기록하는 2차원 배열이 필요 없이, 1차원 배열로 저장하면 된다. 아래는 코드의 내용과 참고 블로그를 적어놓았다.
from collections import Counter
def solution(points, routes):
def bfs(route):
time = 0
robot_loc = []
for i in range (len(route)-1):
sx,sy = points[route[i]-1]
ex,ey = points[route[i+1]-1]
while sx != ex:
robot_loc.append((sx, sy, time))
if sx < ex:
sx += 1
else:
sx -= 1
time += 1
while sy != ey:
robot_loc.append((sx, sy, time))
if sy < ey:
sy += 1
else:
sy -= 1
time += 1
robot_loc.append((sx, sy, time)) # 종착지 좌표 추가
return robot_loc
res = []
for route in routes:
res.extend(bfs(route))
temp = Counter(res)
answer = 0
for i in temp.values():
if i>= 2:
answer +=1
return answer
'알고리즘 문제 리뷰' 카테고리의 다른 글
| PCCE 후기 및 기출문제 리뷰 (0) | 2025.01.14 |
|---|
