문제
어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.
- 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는 n개의 포인트가 존재합니다. 각 포인트는 1~n까지의 서로 다른 번호를 가집니다.
- 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
- 운송 시스템에 사용되는 로봇은 x대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
- 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
- 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.
이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.
운송 포인트 n개의 좌표를 담은 2차원 정수 배열 points와 로봇 x대의 운송 경로를 담은 2차원 정수 배열 routes가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
2 ≤ points의 길이 = n ≤ 100
points[i]는 i + 1번 포인트의 [r 좌표, c 좌표]를 나타내는 길이가 2인 정수 배열입니다.
1 ≤ r ≤ 100
1 ≤ c ≤ 100
같은 좌표에 여러 포인트가 존재하는 입력은 주어지지 않습니다.
2 ≤ routes의 길이 = 로봇의 수 = x ≤ 100
2 ≤ routes[i]의 길이 = m ≤ 100
routes[i]는 i + 1번째 로봇의 운송경로를 나타냅니다. routes[i]의 길이는 모두 같습니다.
routes[i][j]는 i + 1번째 로봇이 j + 1번째로 방문하는 포인트 번호를 나타냅니다.
같은 포인트를 연속으로 방문하는 입력은 주어지지 않습니다.
1 ≤ routes[i][j] ≤ n
나의 해답
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int[,] points, int[,] routes) {
//문제 이해완료
//시간복잡도 괜찮은가?
// => 최대 100개의 포인트, 100대의 로봇 존재. 10000까지 늘어남.
// 만약 최대 경로로 뺑뺑이 돌 시 10000 x 100으로 1,000,000초(배열길이) 까지 늘어날 수 있음.
// 시간복잡도를 가장 최소로 만들려면 어떻게 해야하는가?
// 단순히 0초~최대 1,000,000초까지 각각의 로봇을 비교한다면 최대 100대의 로봇이 존재할 수 있으므로 복잡도는
// 100,000,000 까지 늘어남.
// 모르겠넴... 그냥 한 번 풀어나 보자.
//================================================================================================//
//구현방법
//1. 각각의 로봇의 경로를 큐에 저장
//2. 큐에 넣어놓은 경로를 하나씩 빼내면서 겹치는 경로(충돌위험이있는경로)가 존재하는 지 확인
//2-1. 딕셔너리로 경로를 저장하여 빠르게 계산
//3. 만약 충돌위험이 있으면 result에 1을 추가하여 출력
//3-1. 이미 검출된 위험경로는 다시 검출되어도 상관없지만, 다른 위험경로가 존재할 경우 result에 추가해주어야함.
//딕셔너리 구성 => 키 = 1차원배열[r,c,second] / 값 = 이미 존재하는 로봇이 있는가?
//0 => 아직 충돌위험없음 / 1 => 이미 충돌위험이 있는 자리
int answer = 0;
Dictionary<(int,int,int),int> dangerousCheck = new Dictionary<(int,int,int),int>();
Queue<int[]> routeForSec;
for(int i=0; i < routes.GetLength(0);i++)
{
//routeForSec = CalcRoute(points,routes[i]);
int[] tempRoute = new int[routes.GetLength(1)];
for (int j=0; j < routes.GetLength(1); j++)
{
tempRoute[j] = routes[i,j];
}
routeForSec = CalcRoute(points,tempRoute);
int second = 0;
while(routeForSec.Count > 0)
{
int[] presentPoint = routeForSec.Dequeue();
var key = (presentPoint[0],presentPoint[1],second);
if(!dangerousCheck.ContainsKey(key))
{
dangerousCheck.Add(key,0);
}
else
{
if(dangerousCheck[key]==0)
{
dangerousCheck[key] = 1;
answer++;
}
}
second++;
}
}
return answer;
}
//매개변수가 크면 함수호출에 의한 부하가 커지나? 그건 모르겠음.
public Queue<int[]> CalcRoute(int[,]points, int[]routes)
{
Queue<int[]> routeForSec = new Queue<int[]>();
for(int i = 0; i < routes.Length-1 ; i++)
{
int fromIdx = routes[i]-1;
int toIdx = routes[i + 1]-1;
int sub_R = points[toIdx, 0] - points[fromIdx, 0];
int sub_C = points[toIdx, 1] - points[fromIdx, 1];
int[] tempPoint = new int[points.GetLength(1)];
for(int j = 0; j < points.GetLength(1); j++)
{
tempPoint[j] = points[fromIdx,j];
}
int[] presentPoint = tempPoint;
if( i == 0)
{
routeForSec.Enqueue((int[])presentPoint.Clone());
}
while(sub_R != 0)
{
if(sub_R > 0)
{
//presentPoint += dir_R;
presentPoint[0] += 1;
sub_R--;
routeForSec.Enqueue((int[])presentPoint.Clone());
}
else if(sub_R<0)
{
presentPoint[0] -= 1;
sub_R++;
routeForSec.Enqueue((int[])presentPoint.Clone());
}
}
while(sub_C != 0)
{
if(sub_C > 0)
{
//presentPoint += dir_R;
presentPoint[1] += 1;
sub_C--;
routeForSec.Enqueue((int[])presentPoint.Clone());
}
else if(sub_C<0)
{
presentPoint[1] -= 1;
sub_C++;
routeForSec.Enqueue((int[])presentPoint.Clone());
}
}
}
return routeForSec;
}
}과정
1. 처음엔 모든 로봇들의 이동경로를 각각 비교했을때의 시간복잡도를 생각했다.
- 좌표는 100 x 100까지 나올 수 있으며, 로봇은 최대 100대까지 존재할 수 있다. 또한, 로봇이 이동할 수 있는 포인트는 100개까지 존재하고, 루트 또한 최대 100개까지 존재한다.
- 만약, 로봇들의 개수가 최대(100개)이고, 최대 개수의 포인트들을 최대한 많이 이동한다고 생각해보자.
- 한 포인트에서 다른 포인트로 이동할 수 있는 거리는 최대 [0,0]에서 [99,99] 이므로, 길이가 199인 배열이 나올 것이다.
- 포인트 사이의 이동은 최대 99번 이루어 질 수 있으므로, 19,701회가 하나의 로봇에서 나올 수 있는 최대 이동횟수이다.
- 로봇은 최대 100대 까지 존재하므로, 각각의 로봇들끼리 충돌 위험을 모두 비교하면 19,701! 이 나올 것이다.
- 단순하게 충돌위험을 감지하기 위해서 모든 로봇들에 대하여 충돌위험을 감지하는 것은 큰 연산비용이 나온다는 것을 알았다.
2. 시간복잡도를 줄이기 위해서, 로봇들의 이동경로를 검색하기 위한 Dictionary자료형을 만들기로 하였다.
- Ditionary를 만들어서 키를 (r좌표,c좌표,시간)으로 하고, 값을 충돌위험이 있는지 판단하는 int값으로 만들었다.
- 로봇들의 경로를 읽으면서, 로봇들이 이동하는 좌표들을 모두 딕셔너리에서 검색하고 만약 키값이 존재하지않으면 등록한다. 이때 값을 0으로 한다.
- 로봇의 이동경로를 딕셔너리에서 검색했을 때, value를 확인해본다.
- value가 0인경우 => 이미 다른 로봇의 이동경로이면서 아직 충돌위험이 감지되지 않은 경로이므로, 충돌위험이 1증가하고, 이미 검출된 충돌위험경로라는 표시로 값을 1로 바꾼다.
- value가 1인경우 => 이미 충돌위험이 감지된 이동경로이므로, 충돌위험을 1증가시킬 필요가 없다.
3. 로봇들의 이동경로를 계산하기 위해서 CalcRoute라는 메서드를 만들었다.
- 로봇들은 매 초마다 포인트에서 다른 포인트로 이동하기 때문에, 포인트와 이동하는 경로인 route를 매개변수로 받았다.
- 리턴 값은 이동경로를 앞에서부터 차례대로 다시 꺼내야하므로, Queue자료구조로 하였다.
문제점
문제를 풀이하면서 너무나 많은 문제점이 발생하여, 짠 코드를 갖고 클로드코드에게 코드에 대한 문제를 알려달라고 하였다.
단순한 문법적인 문제점
- Dequeue → Dequeue() — 메서드이므로 괄호 필요
- HasKey → ContainsKey — Dictionary에는 HasKey가 없습니다. => 다른 언어와 헷갈렸다..
- Dictionary 키 조회 방식 — int[]는 참조 비교라서 키로 쓰면 제대로 동작하지 않습니다. 좌표+시간을 튜플이나 문자열로 만들어야 합니다.
// 잘못
dangerousCheck.HasKey(presentPoint[0], presentPoint[1], second)
// 수정 (튜플 사용)
var key = (presentPoint[0], presentPoint[1], second);
dangerousCheck.ContainsKey(key)- routes[i]로 1차원 행 추출 — 2차원 배열에서는 routes[i]로 행을 꺼낼 수 없습니다
// 잘못 (CalcRoute의 두 번째 매개변수가 int[]인데 routes[i]는 안 됨)
CalcRoute(points, routes[i]);
// 수정 - 행을 직접 복사
int[] route = new int[routes.GetLength(1)];
for (int j = 0; j < routes.GetLength(1); j++)
route[j] = routes[i, j];
CalcRoute(points, route);- points[i][0] → points[i,0] — 2차원 배열은 [][]가 아니라 [,]입니다.
// 잘못
points[i+1][0]
points[i][0]
// 수정
points[i+1, 0]
points[i, 0]- presentPoint 배열을 복사 없이 재사용
// ❌ 현재: 같은 배열 참조를 계속 Enqueue
routeForSec.Enqueue(presentPoint);
presentPoint[0] += 1;
routeForSec.Enqueue(presentPoint); // 위에 넣은 것도 같이 바뀜
// ✅ 수정: Enqueue할 때마다 복사본을 넣어야 함
routeForSec.Enqueue((int[])presentPoint.Clone());
presentPoint[0] += 1;
routeForSec.Enqueue((int[])presentPoint.Clone());Logic에서의 문제점
경유지 간 이동에서 도착점이 중복 enqueue
내가 기존의 짠 코드의 경우,
...
...
...
for(int j = 0; j < points.GetLength(1); j++)
{
tempPoint[j] = points[fromIdx,j];
}
int[] presentPoint = tempPoint;
routeForSec.Enqueue((int[])presentPoint.Clone());
...
...
...
하나의 포인트에서 다른 포인트로 이동하는 경로를 계산하는 과정에서 시작위치를 큐에 집어 넣었다.
이때의 문제는, 첫 지점에서는 0초에서 해당 위치에 있었으므로 큐에 시작위치를 집어넣는 것이 맞는데, 한 번 이상 이동한 이후에 다른 포인트로 이동하는 과정에서 도착점위치를 이미 enqueue했음에도
다시 반복문을 돌기시작할 때, 시작점 = 도착점임에도 다시 시작점을 enqueue해버린 것이다. 마치 해당 위치에 로봇이 2초동안 머무른 것 같은 효과를 준다.
수정 코드)
// 첫 구간에서만 출발점을 넣음
if(i == 0)
{
routeForSec.Enqueue((int[])presentPoint.Clone());
}수정방법은 첫 반복을 제외하고, 시작점을 enqueue하지 않는 것이다.
최소한 한번의 동작을 보장하는 do-while문을 사용해도 괜찮았을 것 같다.
반성
-
2차원배열을 많이 안써봐서 2차원 배열에서 가능한 것과 가능하지 않은 것을 잘 몰랐다.
다른 언어에서는 2차원 배열끼리의 연산을 제공하는 경우도 있었기 때문에 2차원배열 연산에 대한 문제나 2차원 배열에 접근하는것등이 생각보다 어려웠다. -
참조에 의한 값을 연산에 사용하여, 의도와는 다른 연산이 이루어진 경우가 많았다.
참조형식과 값형식은 이미 많이 배우고 들은 내용인데, 좀 생각없이 코드를 짰던 것 같다.
소감
프로그래머스 lv2 문제는 최근에 별로 풀어보지않았는데, 생각보다 너무 오래걸리고 어려웠다. 꾸준히 문제를 풀어보며 감을 익히는게 중요한 것 같다.
게임개발자 취준생입니다