[Programmers] PCCP 기출문제 3번 / 충돌위험 찾기 - LV 2
접근
- 구현
풀이
PCCP 기출문제의 3번 충돌위험 찾기 문제로 프로그래머스 레벨 2로 측정된 문제이다. 모든 로봇이 동시에 주어진 경로를 통해 움직일 때 충돌이 일어나는 횟수를 구하는 문제로 주목할 부분은 주어진 경로, 경유해야 할 포인트는 여러 개가 될 수 있다는 점과 최단 경로 이동을 위해 좌표는 r 이 항상 우선으로 이동해야 한다. 충돌의 경우 2대 이상의 로봇이 같은 좌표일 경우 충돌이 일어난 것이고 같은 좌표에 로봇이 몇 대가 있던 한 번의 충돌로 치며 같은 시간 다른 곳에서 일어난 충돌은 별도의 충돌로 4초 경 로봇 1, 3, 5이 (1, 2)에서 충돌하고 로봇 2, 4가 (5, 4)에서 충돌한 경우 4초에는 총 두 번 충돌이 일어난 것이 된다. 문제 설명에 GIF로 아주 잘 설명이 되어 있어 이해하는데 문제는 없을 것이다.
private static class Robot {
private int r;
private int c;
private int nextStopover;
public Robot(int r, int c, int nextStopover) {
this.r = r;
this.c = c;
this.nextStopover = nextStopover;
}
public void rPlus() {
this.r++;
}
public void rMinus() {
this.r--;
}
public void cPlus() {
this.c++;
}
public void cMinus() {
this.c--;
}
public void stopoverPlus() {
this.nextStopover++;
}
}이번 문제를 풀 때 사용할 로봇의 정보를 저장하는 클래스로 로봇의 현재 r, c 좌표 그리고 다음 경유지 필드를 가진다. 현재 코드는 처음 문제를 풀 때 사용했던 것으로 간단하게 값들을 조작하는 메서드만 만들어두고 메인 코드에서 로직을 구현했는데 너무 복잡한 거 같아 리팩토링을 좀 했다.
private class Robot {
private int r;
private int c;
private int nextStopover;
public Robot(int r, int c, int nextStopover) {
this.r = r;
this.c = c;
this.nextStopover = nextStopover;
}
public void moveToTarget(int targetR, int targetC) {
if (r < targetR) {
r++;
return;
} else if (r > targetR) {
r--;
return;
}
if (c < targetC) {
c++;
} else if (c > targetC) {
c--;
}
}
public boolean hasArrived(int targetR, int targetC) {
return r == targetR && c == targetC;
}
public void stopoverPlus() {
nextStopover++;
}
}리팩토링을 한 코드로 메인에 있던 로직을 집어넣었고 풀이는 리팩토링 된 코드로 진행할 예정이다.
int routeStep = routes[0].length;
List<Robot> robots = new ArrayList<>();
Map<Integer, Integer> startCollisions = new HashMap<>();
for (int[] route : routes) {
int startPoint = route[0] - 1;
int r = points[startPoint][0];
int c = points[startPoint][1];
robots.add(new Robot(r, c, 1));
startCollisions.merge(route[0], 1, Integer::sum);
}
int result = 0;
for (Integer value : startCollisions.values()) {
if (value > 1) {
result++;
}
}우선 routeStep 변수는 총 경유지의 개수를 나타내는 변수로 로봇이 모든 경유지를 다 돌았는지 체크를 위해 사용한다. 로봇 리스트를 시작점 좌표로 채워주며 초기 시작 위치에서의 충돌을 체크하기 위해 좌표를 맵에 넣어주게 된다. 맵을 순회하며 같은 좌표가 2개 이상인 경우 충돌이 일어났으므로 충돌 횟수를 늘려준다.
while (!robots.isEmpty()) {
Map<String, Integer> collisionMap = new HashMap<>();
boolean[] arrived = new boolean[robots.size()];모든 로봇이 목적지에 도착할 때까지 반복이 시작되고 충돌 체크를 위한 맵과 모든 로봇이 도착했는지 체크를 위한 배열을 선언한다.
for (int i = 0; i < robots.size(); i++) {
Robot robot = robots.get(i);
int nextStopover = robot.nextStopover;
if (nextStopover >= routeStep) {
arrived[i] = true;
continue;
}모든 로봇을 순회 하며 이동 처리를 해주는데 다음 경유지와 총 경유지 개수를 비교해 목적지에 도달한 상태라면 도착 체크를 해준 뒤 다음 로봇 처리로 넘어간다.
int pointIndex = routes[i][nextStopover] - 1;
int targetR = points[pointIndex][0];
int targetC = points[pointIndex][1];
robot.moveToTarget(targetR, targetC);목적지가 아니라면 다음 경유지 혹은 목적지의 좌표값을 찾아와서 로봇을 움직여준다.
public void moveToTarget(int targetR, int targetC) {
if (r < targetR) {
r++;
return;
} else if (r > targetR) {
r--;
return;
}
if (c < targetC) {
c++;
} else if (c > targetC) {
c--;
}
}moveToTarget 메서드는 현재 좌표값과 목적지 좌표값을 비교해 로봇을 움직여 주는 메서드로 r 값이 우선으로 움직여지기 때문에 목적지와 값을 비교한 후 목적지 방향으로 이동시켜 줬다. 한 번에 한 칸의 움직임만 가능하기 때문에 r 좌표를 이동한 경우 return 하여 주고 r 좌표가 이동되지 않은 경우 c 좌표를 이동한다.
String posKey = robot.r + " " + robot.c;
collisionMap.merge(posKey, 1, Integer::sum);
if (robot.hasArrived(targetR, targetC)) {
robot.stopoverPlus();
}
}이동한 후에 현재 좌표를 키 값으로 충돌 감지 맵에 넣어주고 경유지나 목적지에 도착한 경우 다음 경유지로 바꿔준다.
for (Integer value : collisionMap.values()) {
if (value > 1) {
result++;
}
}로봇의 움직임 처리가 끝나면 맵을 순회하며 충돌이 일어난 부분들을 체크해준다.
boolean allArrived = true;
for (boolean arrivedStatus : arrived) {
if (!arrivedStatus) {
allArrived = false;
break;
}
}
if (allArrived) {
break;
}도착 체크 배열을 순회하며 모든 로봇이 도착했는지 체크 후 모든 로봇이 도착한 경우 반복을 종료한다.
전체 코드
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private class Robot {
private int r;
private int c;
private int nextStopover;
public Robot(int r, int c, int nextStopover) {
this.r = r;
this.c = c;
this.nextStopover = nextStopover;
}
public void moveToTarget(int targetR, int targetC) {
if (r < targetR) {
r++;
return;
} else if (r > targetR) {
r--;
return;
}
if (c < targetC) {
c++;
} else if (c > targetC) {
c--;
}
}
public boolean hasArrived(int targetR, int targetC) {
return r == targetR && c == targetC;
}
public void stopoverPlus() {
nextStopover++;
}
}
public int solution(int[][] points, int[][] routes) {
int routeStep = routes[0].length;
List<Robot> robots = new ArrayList<>();
Map<Integer, Integer> startCollisions = new HashMap<>();
for (int[] route : routes) {
int startPoint = route[0] - 1;
int r = points[startPoint][0];
int c = points[startPoint][1];
robots.add(new Robot(r, c, 1));
startCollisions.merge(route[0], 1, Integer::sum);
}
int result = 0;
for (Integer value : startCollisions.values()) {
if (value > 1) {
result++;
}
}
while (!robots.isEmpty()) {
Map<String, Integer> collisionMap = new HashMap<>();
boolean[] arrived = new boolean[robots.size()];
for (int i = 0; i < robots.size(); i++) {
Robot robot = robots.get(i);
int nextStopover = robot.nextStopover;
if (nextStopover >= routeStep) {
arrived[i] = true;
continue;
}
int pointIndex = routes[i][nextStopover] - 1;
int targetR = points[pointIndex][0];
int targetC = points[pointIndex][1];
robot.moveToTarget(targetR, targetC);
String posKey = robot.r + " " + robot.c;
collisionMap.merge(posKey, 1, Integer::sum);
if (robot.hasArrived(targetR, targetC)) {
robot.stopoverPlus();
}
}
for (Integer value : collisionMap.values()) {
if (value > 1) {
result++;
}
}
boolean allArrived = true;
for (boolean arrivedStatus : arrived) {
if (!arrivedStatus) {
allArrived = false;
break;
}
}
if (allArrived) {
break;
}
}
return result;
}
}'알고리즘 > 코딩테스트-Programmers' 카테고리의 다른 글
| [Programmers] [1차] 캐시 - JAVA (1) | 2024.09.19 |
|---|---|
| [Programmers] PCCP 기출문제 4번 / 수식 복원하기 Java (2) | 2024.09.18 |
| [Programmers] PCCE 기출문제 10번 / 공원 Java (1) | 2024.09.16 |
| [Programmers] PCCP 기출문제 2번 / 퍼즐 게임 챌린지 Java (1) | 2024.09.16 |
| [Programmers] PCCP 기출문제 1번 / 동영상 재생기 JAVA (0) | 2024.09.15 |