충돌 위험 찾기
문제 설명
어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.
1. 물류 센터에는 (r,c)와 같이 2차원 좌표로 나타낼 수 있는n개의 포인트가 존재합니다. 각 포인트는1~n까지의 서로 다른 번호를 가집니다.
2. 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
3. 운송 시스템에 사용되는 로봇은x대이고, 모든 로봇은 0초에 동시에 출발합니다.
로봇은 1초마다r좌표와c좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다.
4. 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우,r좌표가 변하는 이동을c좌표가 변하는 이동보다 먼저 합니다.
5. 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다.
관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다.
만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.운송 포인트
n개의 좌표를 담은 2차원 정수 배열points와 로봇x대의 운송 경로를 담은 2차원 정수 배열routes가 매개변수로 주어집니다.
이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를return하도록solution함수를 완성해 주세요.
풀이
전체 코드
public class CollisionChecker
{
private static int arriveCount = 0;
private static int collsionCount = 0;
private static List<Robot> robots = new List<Robot>();
private static Dictionary<Tuple<int,int>, int> map = new Dictionary<Tuple<int,int>, int>();
private static Action onMove = () => { };
public static int Solution(int[,] points, int[,] routes)
{
int robotCount = routes.GetLength(0);
//이동할 로봇을 생성
for (int i = 0; i < robotCount; i++)
{
int[] robotRoute = new int[routes.GetLength(1)];
for (int j = 0; j < robotRoute.Length; j++)
{
robotRoute[j] = routes[i, j];
}
Robot tempRobot = new Robot(i, points, robotRoute, Arrive, map);
onMove += tempRobot.Move;
robots.Add(tempRobot);
}
CheckRobotCollision();
while (arriveCount < robotCount)
{
//로봇 이동 처리
onMove.Invoke();
CheckRobotCollision();
}
return collsionCount;
}
private static void Arrive(int index)
{
arriveCount++;
onMove -= robots[index].Move;
}
private static void CheckRobotCollision()
{
foreach (var count in map.Values)
{
if (count > 1)
{
collsionCount++;
}
}
}
}
class Robot
{
private int _index;
private int[,] _points;
private int[] _routes;
private int _routeIndex = 0;
private Tuple<int, int> _nextPos;
private bool _isArrived = false
private static Dictionary<Tuple<int, int>, int> _map;
public Tuple<int, int> CurrentPos { get; private set; }
private Action<int> _onArrived;
public Robot(int index, int[,] points, int[] routes, Action<int> onArrived, Dictionary<Tuple<int, int>, int> map)
{
_index = index;
_points = points;
_routes = routes;
CurrentPos = new Tuple<int, int>(points[routes[_routeIndex] - 1, 0], points[routes[_routeIndex] - 1, 1]);
SetNextPos();
_onArrived = onArrived;
_map = map;
if (_map.ContainsKey(CurrentPos))
{
_map[CurrentPos]++;
}
else
{
_map.Add(CurrentPos, 1);
}
}
private void SetNextPos()
{
_routeIndex++;
if (_routeIndex >= _routes.Length)
{
if (!_isArrived)
{
_isArrived = true;
return;
}
if (_isArrived)
{
_onArrived.Invoke(_index);
if (_map.ContainsKey(CurrentPos))
{
_map[CurrentPos]--;
}
}
return;
}
_nextPos = new Tuple<int, int>(_points[_routes[_routeIndex] - 1, 0], _points[_routes[_routeIndex] - 1, 1]);
}
public void Move()
{
//기존에 있던 위치에서 벗어났으므로 제거
if (_map.ContainsKey(CurrentPos))
{
_map[CurrentPos]--;
}
//r값을 먼저 이동
if (CurrentPos.Item1 != _nextPos.Item1)
{
if (CurrentPos.Item1 < _nextPos.Item1)
CurrentPos = new Tuple<int, int>(CurrentPos.Item1 + 1, CurrentPos.Item2);
else
CurrentPos = new Tuple<int, int>(CurrentPos.Item1 - 1, CurrentPos.Item2);
}
//r값이 맞춰진 후 c 값을 이동
else if (CurrentPos.Item2 != _nextPos.Item2)
{
if (CurrentPos.Item2 < _nextPos.Item2)
CurrentPos = new Tuple<int, int>(CurrentPos.Item1, CurrentPos.Item2 + 1);
else
CurrentPos = new Tuple<int, int>(CurrentPos.Item1, CurrentPos.Item2 - 1);
}
//새로운 위치에 위치했다는 것을 map에 전달
if (_map.ContainsKey(CurrentPos))
{
_map[CurrentPos]++;
}
else
{
_map.Add(CurrentPos, 1);
}
//목적지에 도착했다면 다음 목적지를 탐색
if (CurrentPos.Equals(_nextPos))
{
SetNextPos();
}
}
}- 지난 문제에 이어 설명이 복잡한 문제가 제시됨
- 다리를 지나는 트럭 문제에서 사용했던 것처럼 여기서도 로봇 클래스를 따로 만들어주고 이동과 도착 처리에 대해서는 델리게이트를 통해 한번에 처리하는 방식을 사용
전역 변수
private static int arriveCount = 0;
private static int collsionCount = 0;
private static List<Robot> robots = new List<Robot>();
private static Dictionary<Tuple<int,int>, int> map = new Dictionary<Tuple<int,int>, int>();
private static Action onMove = () => { };- 도착한 로봇의 수를 통해 전체 계산 로직이 끝날 지점을 확인할 수 있도록 하였고, 위험 상황 발생 횟수를
collsionCount를 통해 확인 - 현재 운행 중인 로봇을 관리할 리스트인
robots를 선언했으나 전체에서 결국 델리게이트 해제 용도로 밖에 사용하지 않아 불필요해 보임 - 각각의 좌표에 위치한 로봇의 수를 통해 위험 상황을 확인할 수 있도록 하는
map을 선언 - 전체 로봇의 이동 로직을 한 번에 실시할 수 있도록
onMove델리게이트 선언
로봇 생성
int robotCount = routes.GetLength(0);
//이동할 로봇을 생성
for (int i = 0; i < robotCount; i++)
{
int[] robotRoute = new int[routes.GetLength(1)];
for (int j = 0; j < robotRoute.Length; j++)
{
robotRoute[j] = routes[i, j];
}
Robot tempRobot = new Robot(i, points, robotRoute, Arrive, map);
onMove += tempRobot.Move;
robots.Add(tempRobot);
}routes내의 각각의 배열의 개수가 결국 로봇의 수를 의미하므로 전체 로봇의 숫자를 확인routes가 정수 배열의 배열이었다면 보다 쉬웠겠지만 다차원 배열 형태이므로 다른 차원의 길이를 통해 각각의 로봇에 할당된 경로의 길이를 확인- 이를
robotRoute로 재구성해 정수 배열로 변환하여 로봇을 생성할 때 정보를 전달 - 각각의 지점에 대한 정보와 로봇이 이동할 루트 그리고 도착했을 때 실행할 델리게이트와 이동 중에 현재 위치를 입력할
map을 입력 - 로봇의
Move함수를onMove델리게이트에 등록 후 리스트에도 추가
충돌 확인
...
//최초 시작지점에서의 충돌 위험 확인
CheckRobotCollision();
while (arriveCount < robotCount)
{
//로봇 이동 처리
onMove.Invoke();
CheckRobotCollision();
}
return collsionCount;
}
private static void CheckRobotCollision()
{
foreach (var count in map.Values)
{
if (count > 1)
{
collsionCount++;
}
}
}- 로봇을 배치한 후 이동이 실행되기 전, 최초 지점에서의 충돌 위험을 확인한 후 모든 로봇이 도착할 때까지 이동과 충돌 확인을 반복
- 충돌 위험 여부는
(r,c)좌표에 로봇이 이동하며 자신의 위치를 표시하고 해당 위치에 있는 로봇의 숫자가 1보다 클 경우 충돌 위험으로 인식하여collsionCount에 값을 더함
로봇 클래스
전역 변수
private int _index;
private int[,] _points;
private int[] _routes;
private int _routeIndex = 0;
private Tuple<int, int> _currentPos;
private Tuple<int, int> _nextPos;
private bool _isArrived = false
private static Dictionary<Tuple<int, int>, int> _map;
private Action<int> _onArrived;- 로봇을 구분하기 위한 인덱스와 이동 지점들 그리고 자신의 이동 루트를 저장
- 현재 목적지를 확인하기 위해 루트의 어떤 인덱스를 확인하고 있는지를
_routeIndex를 통해 확인 _currentPos와'_nextPos를 통해 현재 위치와 이동할 목표 지점을 저장- 목적지에 도착했는지 여부를
_isArrived를 통해 확인하고 앞서 메인 로직 클래스에서 선언한map을 참조할_map과 도착시 호출할 메서드를 등록할_onArrived델리게이트 선언
생성자
public Robot(int index, int[,] points, int[] routes, Action<int> onArrived, Dictionary<Tuple<int, int>, int> map)
{
_index = index;
_points = points;
_routes = routes;
_currentPos = new Tuple<int, int>(points[routes[_routeIndex] - 1, 0], points[routes[_routeIndex] - 1, 1]);
SetNextPos();
_onArrived = onArrived;
_map = map;
if (_map.ContainsKey(_currentPos))
{
_map[_currentPos]++;
}
else
{
_map.Add(_currentPos, 1);
}
}- 로봇을 생성하기 위해 입력한 변수들을 저장하고 맵에 현재 위치를 등록
로봇 이동 함수
public void Move()
{
//기존에 있던 위치에서 벗어났으므로 제거
if (_map.ContainsKey(_currentPos))
{
_map[_currentPos]--;
}
//r값을 먼저 이동
if (_currentPos.Item1 != _nextPos.Item1)
{
if (_currentPos.Item1 < _nextPos.Item1)
_currentPos = new Tuple<int, int>(_currentPos.Item1 + 1, _currentPos.Item2);
else
_currentPos = new Tuple<int, int>(_currentPos.Item1 - 1, _currentPos.Item2);
}
//r값이 맞춰진 후 c 값을 이동
else if (_currentPos.Item2 != _nextPos.Item2)
{
if (_currentPos.Item2 < _nextPos.Item2)
_currentPos = new Tuple<int, int>(_currentPos.Item1, _currentPos.Item2 + 1);
else
_currentPos = new Tuple<int, int>(_currentPos.Item1, _currentPos.Item2 - 1);
}
//새로운 위치에 위치했다는 것을 map에 전달
if (_map.ContainsKey(_currentPos))
{
_map[_currentPos]++;
}
else
{
_map.Add(_currentPos, 1);
}
//목적지에 도착했다면 다음 목적지를 탐색
if (_currentPos.Equals(_nextPos))
{
SetNextPos();
}
}- 기존 위치에서 벗어날 것이므로 맵에서 기존 위치에 해당하는 값을 하나 제거
- 조건에서
r값을c값보다 먼저 변경한다는 규칙이 있었으므로r값에 해당하는 값부터 목적지 값에 맞도록 변경, 이후 같은 방식으로c값도 변경 - 새로운 위치에 이동한 것을 맵에 전달하고 해당 좌표에 해당하는 값을 더함
_nextPos에 도착했다면 다음 목적지를 설정
다음 목적지 설정 함수
private void SetNextPos()
{
_routeIndex++;
if (_routeIndex >= _routes.Length)
{
if (!_isArrived)
{
_isArrived = true;
return;
}
if (_isArrived)
{
_onArrived.Invoke(_index);
if (_map.ContainsKey(_currentPos))
{
_map[_currentPos]--;
}
}
return;
}
_nextPos = new Tuple<int, int>
(_points[_routes[_routeIndex] - 1, 0],
_points[_routes[_routeIndex] - 1, 1]);
}- 찾고자 하는 목적지를 인덱스를 통해 확인할 수 있으므로 루트의 인덱스를 하나 더해 루트 배열에서 해당 값에 해당하는 좌표 값을 가져와 목적지로 입력
(_routes[_routeIndex] - 1에서 1을 빼주는 이유는 루트 배열에서 0부터 시작하는 인덱스가 아니라 1부터 시작하는 인덱스로 루트를 표현하고 있기 때문에 1을 빼줌) - 만약 찾고자 하는 루트 인덱스가 루트 배열의 범위를 벗어난다면 최종 목적지에 도달했다는 것이므로 도착했다는
bool변수를 갱신 - 최종적으로 맵에서 벗어날 때는 도착 후 다시 이동 입력이 들어왔을 때 맵에서 완전히 벗어나도록 실시
(도착 지점에서의 충돌 위험도 확인하기 위함)
