프로그래머스 | Level 2 | 충돌위험 찾기
Programmers | Level 2 | 충돌위험 찾기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Breadth-First Search
Description
어떤 물류 센터는 로봇을 이용한 자동 운송 시스템을 운영합니다. 운송 시스템이 작동하는 규칙은 다음과 같습니다.
- 물류 센터에는 (r, c)와 같이 2차원 좌표로 나타낼 수 있는
n
개의 포인트가 존재합니다. 각 포인트는 1~n
까지의 서로 다른 번호를 가집니다. - 로봇마다 정해진 운송 경로가 존재합니다. 운송 경로는 m개의 포인트로 구성되고 로봇은 첫 포인트에서 시작해 할당된 포인트를 순서대로 방문합니다.
- 운송 시스템에 사용되는 로봇은
x
대이고, 모든 로봇은 0초에 동시에 출발합니다. 로봇은 1초마다 r 좌표와 c 좌표 중 하나가 1만큼 감소하거나 증가한 좌표로 이동할 수 있습니다. - 다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.
- 마지막 포인트에 도착한 로봇은 운송을 마치고 물류 센터를 벗어납니다. 로봇이 물류 센터를 벗어나는 경로는 고려하지 않습니다.
이동 중 같은 좌표에 로봇이 2대 이상 모인다면 충돌할 가능성이 있는 위험 상황으로 판단합니다. 관리자인 당신은 현재 설정대로 로봇이 움직일 때 위험한 상황이 총 몇 번 일어나는지 알고 싶습니다. 만약 어떤 시간에 여러 좌표에서 위험 상황이 발생한다면 그 횟수를 모두 더합니다.
운송 포인트 n
개의 좌표를 담은 2차원 정수 배열 points
와 로봇 x
대의 운송 경로를 담은 2차원 정수 배열 routes
가 매개변수로 주어집니다. 이때 모든 로봇이 운송을 마칠 때까지 발생하는 위험한 상황의 횟수를 return
하도록 solution
함수를 완성해 주세요.
Constraints
- 2 ≤
points
의 길이 =n
≤ 100points[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
- 2 ≤
Examples
points | routes | result |
---|---|---|
[[3, 2], [6, 4], [4, 7], [1, 4]] | [[4, 2], [1, 3], [2, 4]] | 1 |
[[3, 2], [6, 4], [4, 7], [1, 4]] | [[4, 2], [1, 3], [4, 2], [4, 3]] | 9 |
[[2, 2], [2, 3], [2, 7], [6, 6], [5, 2]] | [[2, 3, 4, 5], [1, 3, 4, 5]] | 0 |
Solutions
Code
import java.util.*;
class Solution {
// 이동을 위한 방향 델타 배열
private static final int[] dx = {1, -1, 0, 0};
private static final int[] dy = {0, 0, 1, -1};
private static final int length = 101; // 좌표의 최대 크기 (0 <= r, c < 101)
public int solution(int[][] points, int[][] routes) {
Map<String, Integer> moves = new HashMap<>(); // 각 좌표와 도달 시간을 키로 하는 맵
// 각 로봇의 경로를 순차적으로 탐색
for (int[] route : routes) {
int time = 0; // 경로 시작 시간 초기화
for (int i = 0; i < route.length - 1; i++) {
int[] start = points[route[i] - 1]; // 시작 포인트
int[] target = points[route[i + 1] - 1]; // 다음 포인트
bfs(start, target, time, moves); // BFS로 최단 경로 탐색 및 기록
// 경로 구간 종료 후 소요 시간을 누적
time += Math.abs(start[0] - target[0]) + Math.abs(start[1] - target[1]);
}
}
// 충돌 횟수 계산
int crash = 0;
for (int val : moves.values()) {
if (val > 1) crash++; // 동일 시간에 동일 좌표를 여러 로봇이 방문한 경우 충돌 발생
}
return crash; // 최종 충돌 횟수 반환
}
// BFS를 사용하여 최단 경로 탐색 및 경로 기록
private void bfs(int[] start, int[] target, int time, Map<String, Integer> moves) {
Deque<int[]> queue = new ArrayDeque<>(); // BFS 탐색 큐
boolean[][] marked = new boolean[length][length]; // 좌표 방문 여부
Map<String, int[]> paths = new HashMap<>(); // 경로 추적을 위한 맵, 다음 좌표를 키로 설정
queue.offer(new int[]{start[0], start[1], 0}); // 시작 위치 큐에 추가
marked[start[0]][start[1]] = true; // 시작 위치 방문 표시
int step = 0; // 최단 거리 추적용 변수
while (!queue.isEmpty()) {
int[] curr = queue.poll(); // 현재 좌표 및 이동 횟수
int cx = curr[0], cy = curr[1], cs = curr[2];
// 목표 위치에 도달 시 최단 거리 저장 후 반복 종료
if (target[0] == cx && target[1] == cy) {
step = cs;
break;
}
// 상하좌우로 이동하여 새로운 좌표 탐색
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
int ns = cs + 1;
// 좌표가 유효하고 아직 방문하지 않았다면
if (nx >= 0 && nx < length && ny >= 0 && ny < length && !marked[nx][ny]) {
queue.offer(new int[]{nx, ny, ns}); // 큐에 새로운 좌표 추가
marked[nx][ny] = true; // 방문 표시
paths.put(generateKey(nx, ny), new int[]{cx, cy}); // 이전 위치 저장
}
}
}
// 경로를 역추적하여 각 좌표와 시간을 기록
int[] prev = target;
while (step > 0) {
String key = generateKey(prev, step + time); // 고유 키 생성 (좌표와 시간 포함)
moves.put(key, moves.getOrDefault(key, 0) + 1); // 해당 좌표의 방문 횟수 증가
prev = paths.get(generateKey(prev[0], prev[1])); // 이전 좌표로 이동
step--; // 남은 이동 횟수를 줄이며 역추적 진행
}
// 시작 시간에 시작 위치에 도달한 경우도 기록
if (time == 0) {
String key = generateKey(prev, 0);
moves.put(key, moves.getOrDefault(key, 0) + 1);
}
}
private String generateKey(int[] point, int time) {
return time + "," + point[0] + "," + point[1];
}
private String generateKey(int r, int c) {
return r + "," + c;
}
}
Approaches
이 문제는 각 로봇이 최단 경로로 이동할 때 충돌 위험이 발생하는 좌표와 횟수를 파악하는 것입니다. 모든 로봇의 이동 경로를 너비 우선 탐색(BFS)으로 계산하고, 특정 시간에 특정 좌표에 도달하는 경우를 추적하여 충돌 위험을 계산합니다.
1. 문제 분석
주어진 문제는 여러 대의 로봇이 지정된 경로를 따라 최단 거리로 이동할 때, 동일한 시간에 동일한 좌표에 도착하는 상황을 찾아내는 것입니다. 이를 통해 충돌 가능성을 계산하는 것이 목표입니다. 각 로봇의 이동 경로를 추적하면서 경로 상의 위치와 방문 시간을 기록하고, 특정 시간에 같은 좌표에 여러 로봇이 모이는 경우 충돌 횟수를 누적해야 합니다.
로봇이 최단 거리로 이동할 때 출발지와 도착지 사이를 가장 짧은 거리로 이동하되, 최단 경로가 여러 개라면 r 좌표 이동을 우선시하는 규칙을 따릅니다. 이 규칙을 기반으로 각 로봇이 경로를 따라 움직이며, 각 위치에 도착하는 시간을 기록합니다. 이렇게 기록된 정보를 통해 특정 시간에 동일한 좌표에 도착한 로봇이 있는지를 확인하여 충돌 횟수를 계산합니다.
효율적인 경로 추적을 위해 BFS를 사용해 각 로봇의 이동 경로를 최단 거리로 계산하며, 각 위치에 도착하는 시간을 관리합니다. BFS를 통해 이동을 추적하고 시간과 좌표를 동시에 기록하여, 충돌 위험을 효과적으로 파악할 수 있습니다. 이 방법으로 모든 로봇의 이동을 추적하면서 발생하는 충돌 가능성을 빠르고 정확하게 계산할 수 있습니다.
2. 접근 방식
로봇 경로의 충돌 위험을 계산하기 위해 다음과 같은 단계로 접근합니다.
- 로봇 이동 최단 경로 탐색 및 경로 기록: 각 로봇이 지정된 경로의 포인트를 최단 거리로 이동할 수 있도록 BFS로 탐색합니다. 출발지에서 목적지까지의 최단 경로를 구하며, 이동 규칙에 따라 최단 경로가 여러 개일 경우 r 좌표 이동을 우선하여 경로를 설정합니다. 이 과정에서 각 로봇이 지나가는 모든 위치를 고유한 키로 저장해 두고, 이후 최단 이동 경로를 역추적하여 충돌 가능성을 평가하는 데 활용할 수 있도록 합니다.
- 이동 경로 역추적 및 위치별 충돌 기록: 최단 경로 탐색이 완료된 후, 도착지에서 출발지로 경로를 역추적하면서 로봇이 지나간 각 좌표를 확인하고 충돌 가능성을 기록합니다. 이 과정에서 동일한 좌표를 여러 로봇이 지나간 경우를 확인하여 충돌 위험 횟수를 누적할 수 있도록 합니다.
- 위험 상황 체크 및 충돌 횟수 계산: 모든 로봇의 이동 경로를 기록한 후, 각 위치에서 여러 로봇이 동일한 좌표를 지나간 경우를 충돌 위험으로 간주하고, 이러한 충돌 위험 횟수를 누적하여 전체 충돌 위험 횟수를 계산합니다. 이를 통해 로봇 경로 이동 중 발생할 수 있는 충돌 상황을 파악할 수 있습니다.
3. 경로 탐색 델타 배열 초기화
로봇의 최단 거리 탐색을 위해, 이동에 필요한 델타 배열을 설정합니다. r 좌표를 우선으로 하여 이동하므로, 우선적으로 dx 배열에서 r 좌표의 변화를 먼저 설정합니다. 또한 이동 경로의 유효성을 확인하기 위해 최대 100x100 범위에 맞춰 길이를 설정합니다.
private static final int[] dx = {1, -1, 0, 0};
private static final int[] dy = {0, 0, 1, -1};
private static final int length = 101;
4. 로봇 경로 탐색 준비 및 경로 기록 초기화
모든 로봇의 이동 경로를 추적하며 최단 거리로 이동할 수 있도록 초기화합니다. 각 로봇의 경로를 추적하면서, 방문한 각 좌표와 해당 좌표에 도달한 횟수를 기록할 수 있도록 해시맵을 활용해 저장소를 준비합니다. 각 로봇은 지정된 경로를 따라 이동하며, 각 구간의 출발 시각을 기준으로 최단 거리 탐색을 수행합니다. 구간이 종료될 때마다 이동 시간을 누적하여 이후 경로 이동에 반영합니다.
Map<String, Integer> moves = new HashMap<>(); // 각 위치의 방문 횟수를 저장
int time = 0; // 초기 시간 설정
for (int i = 0; i < route.length - 1; i++) {
int[] start = points[route[i] - 1]; // 현재 구간의 시작 위치
int[] target = points[route[i + 1] - 1]; // 현재 구간의 목표 위치
bfs(start, target, time, moves); // BFS로 최단 거리 탐색
time += Math.abs(start[0] - target[0]) + Math.abs(start[1] - target[1]); // 이동 시간 누적
}
5. BFS를 이용한 로봇 이동 최단 경로 탐색
BFS를 사용하여 각 로봇의 최단 경로를 탐색하며, 이동 경로에 포함된 각 위치와 이전 위치를 저장해 두어 이후에 효율적으로 역추적할 수 있도록 합니다. 이때 각 경로의 위치를 해시맵에 저장하고, 다음 좌표를 키로, 이전 좌표를 값으로 설정해 두면, 출발지부터 목적지까지의 전체 경로를 손쉽게 기록하고, 성능을 저해하지 않으면서도 이후에 빠르게 역추적할 수 있습니다.
탐색 시작 시 큐에 출발 좌표를 추가하고, 하나씩 좌표를 꺼내 r 좌표 이동을 우선으로 모든 가능한 방향을 검사합니다. 목표 위치에 도달할 경우 탐색을 종료하고, 최단 거리 값을 저장하여 이후 경로 역추적에 활용할 수 있게 합니다.
private void bfs(int[] start, int[] target, int time, Map<String, Integer> moves) {
Deque<int[]> queue = new ArrayDeque<>(); // BFS 큐 초기화
boolean[][] marked = new boolean[length][length]; // 방문 확인 배열
Map<String, int[]> paths = new HashMap<>(); // 경로 추적을 위한 맵
queue.offer(new int[]{start[0], start[1], 0}); // 시작 좌표를 큐에 추가
marked[start[0]][start[1]] = true; // 시작 위치 방문 표시
int step = 0; // 최단 거리
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int cx = curr[0];
int cy = curr[1];
int cs = curr[2];
// 목표 위치 도달 시
if (target[0] == cx && target[1] == cy) {
step = cs; // 최단 거리 저장 후 탐색 종료
break;
}
// 상하좌우 이동 시도
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
int ns = cs + 1;
if (nx >= 0 && nx < length && ny >= 0 && ny < length && !marked[nx][ny]) {
queue.offer(new int[]{nx, ny, ns}); // 큐에 새로운 좌표 추가
marked[nx][ny] = true; // 현재 좌표 방문 표시
paths.put(generateKey(nx, ny), new int[]{cx, cy}); // 모든 이동 경로 저장 - [키: 다음 좌표, 값: 이전 좌표]
}
}
}
...
}
private String generateKey(int r, int c) {
return r + "," + c; // 좌표를 고유 키로 생성
}
6. 로봇 최단 경로 역추적 및 시간 정보 포함 기록
목표 위치에 도달한 이후, 기록된 경로를 통해 출발지까지 최단 경로를 역추적합니다. 이 과정에서 각 좌표의 방문 횟수를 확인하여, 동일 시간대에 여러 로봇이 동일 좌표를 지나가는 경우 충돌 위험으로 간주할 수 있습니다. 특히 각 좌표의 고유 키 생성 시 시간 정보도 포함해야 충돌 여부를 정확히 판단할 수 있으므로, 모든 좌표와 해당 시간대를 키로 하여 저장해 관리합니다. 이를 통해 다른 로봇이 동일 시간에 같은 위치를 방문할 경우 충돌 횟수가 정확하게 누적됩니다.
private void bfs(int[] start, int[] target, int time, Map<String, Integer> moves) {
...
int[] prev = target; // 목표 위치에서 역추적 시작
while (step > 0) {
String key = generateKey(prev, step + time); // 고유 키 생성 시 좌표와 시간을 결합
moves.put(key, moves.getOrDefault(key, 0) + 1); // 현재 위치의 방문 횟수 누적
prev = paths.get(generateKey(prev[0], prev[1])); // 이전 위치로 이동하여 경로를 역추적
step--; // 남은 이동 횟수를 줄이며 출발지로 향함
}
}
private String generateKey(int[] point, int time) {
return time + "," + point[0] + "," + point[1];
}
7. 로봇 충돌 횟수 계산 후 반환
모든 로봇 경로의 탐색과 경로 추적이 완료되면, 각 위치와 시간에 대한 방문 횟수가 해시맵에 누적되어 있습니다. 이를 바탕으로 동일 시간대에 동일 좌표를 여러 로봇이 방문한 경우를 확인하여 충돌 위험을 계산합니다. 해시맵을 순회하며 방문 횟수가 2 이상인 경우 충돌로 간주하고, 해당 횟수를 누적하여 최종 충돌 횟수를 반환합니다.
int crash = 0;
for (int val : moves.values()) {
if (val > 1) crash++; // 방문 횟수가 2 이상일 경우 충돌 발생
}
return crash; // 총 충돌 횟수 반환
Complexity
- ⏳ TC: O(x * n^2)
- 💾 SC: O(n)
여기서 x는 로봇의 수, n은 각 로봇의 경로 길이를 나타냅니다. 각 로봇마다 BFS를 사용하여 경로를 추적하기 때문에 시간 복잡도는 O(x * n^2)에 비례합니다. 또한, 좌표와 경로를 시간에 따라 기록하기 때문에 공간 복잡도는 각 로봇의 경로 길이에 비례합니다.
- Algorithm
- BFS