[프로그래머스 / JAVA] 충돌위험 찾기

문제 개요

2차원 격자판 위에서 여러 대의 로봇이 정해진 경로를 따라 동시에 이동합니다.
이동 중 "동일한 시간(Turn)에 동일한 좌표(r, c)"에 두 대 이상의 로봇이 존재할 경우 '위험 상황'으로 간주합니다.

이 위험 상황의 총 횟수를 구하는 시뮬레이션 문제입니다.

• 핵심 규칙이동 우선순위: 최단 거리로 이동하되, r(y) 좌표가 먼저 변하는 이동을 c(x) 좌표가 변하는 이동보다 우선합니다.

• 충돌 판정: 특정 시간 $t$에 특정 좌표 $(r, c)$에 2대 이상이 있다면 위험 상황 +1입니다. (3대가 있어도 해당 시간/좌표에서는 1회로 카운트)

• 지연 처리: 로봇마다 경로의 길이가 다르며, 도착한 로봇은 즉시 맵에서 사라집니다.

입력 및 출력

입력:

• points[][]: 포인트 번호별 좌표 정보 (1~100 범위)
• routes[][]: 각 로봇이 방문해야 하는 포인트 번호 순서

출력:

• result: 모든 로봇의 운송이 끝날 때까지 발생한 위험 상황의 총 횟수

접근 방법

1. 왜 "한 로봇씩" 순차적으로 처리했는가?

이 문제는 모든 로봇을 동시에 한 칸씩 움직이는 병렬 방식과, 한 로봇의 전체 경로를 먼저 기록하는 직차 방식 두 가지로 접근할 수 있습니다. 저는 후자(로봇별 순차 처리)를 선택했습니다.

• 구현 복잡도 감소: 병렬 방식은 매 초마다 모든 로봇의 상태를 관리하고 동기화해야 하므로 코드가 비대해집니다. 반면, 한 로봇의 경로를 끝까지 밀고 나가는 방식은 반복문 구조가 단순해져 코드의 직관성이 높아집니다.
• 성능적 이점: 병렬 방식은 매 턴마다 로봇들의 리스트를 순회하며 컨텍스트 스위칭과 유사한 비용이 발생하지만, 순차 방식은 CPU 캐시 효율 측면에서 더 유리하며 불필요한 객체 참조를 줄일 수 있습니다.

2. 메모리 최적화: Sparse Data 관리

전체 맵 크기와 최대 시간을 곱한 $100 \times 100 \times T$ 형태의 3차원 배열은 로봇이 방문하지 않는 빈 공간이 너무 많아 메모리 낭비가 심합니다.

• 지연 생성(Lazy Initialization): Map<Integer, Integer>[][] 구조를 채택하여, 로봇이 실제로 방문한 좌표와 시간에 대해서만 메모리를 할당했습니다.

• 공간 효율성: 배열의 빠른 인덱스 접근([r][c])과 Map의 가변적인 시간축 기록을 결합하여, 메모리 사용량을 최소화하면서도 탐색 속도를 유지했습니다.

3. 충돌 판정 최적화: "실시간 카운팅"

모든 로봇의 경로를 다 기록한 뒤 맵 전체를 다시 훑는 방식은 $O(R \times C \times T)$의 추가 시간이 소요됩니다. 이를 해결하기 위해 기록과 동시에 충돌을 판정하는 로직을 설계했습니다.

• Two-Count Strategy: 특정 좌표/시간에 로봇이 들어올 때 현재 카운트를 확인합니다.
  • Count == 0: 첫 방문, 기록만 수행
  • Count == 1: 두 번째 방문, 이 시점에 즉시 answer++ (위험 상황 확정)
  • Count > 1: 이미 위험 상황이므로 기록만 수행
• 이 로직을 통해 단 한 번의 순회로 모든 충돌 횟수를 정확히 도출했고, 한 좌표에 3대 이상의 로봇이 모여 중복 카운트되는 예외 케이스를 해결했습니다.

코드

import java.util.*;


class Solution {
    public int solution(int[][] points, int[][] routes) {
        int result = 0;
        
        Map<Integer, Integer>[][] map = new HashMap[101][101];
    
        for (int i = 0; i < routes.length; i++) {
            // 특정 경로의 시작 포인트 지정
            int[] cur = points[routes[i][0] - 1];
            int y = cur[0];
            int x = cur[1];
            int turn = 0;
            
            // 첫 좌표에 대한 초기화 및 충돌 감지
            if (map[y][x] == null) map[y][x] = new HashMap<>();
            
            int count = map[y][x].getOrDefault(turn, 0);
            
            if (count == 1) {
                result++;
            }
            
            map[y][x].put(turn, count + 1);
            
            // 특정 경로의 두 번째 포인트부터 마지막 포인트
            for (int j = 1; j < routes[i].length; j++) {
                int[] next = points[routes[i][j] - 1];
                int ny = next[0];
                int nx = next[1];
                
                // 좌표 이동에 대한 로직
                while (y != ny || x != nx) {
                    if (y != ny) {
                        int dy = (y < ny) ? 1 : -1;
                        y += dy;
                    } else {
                        int dx = (x < nx) ? 1 : -1;
                        x += dx;
                    }

                    turn++;

					// 이동한 좌표에 대한 충돌 감지
                    if (map[y][x] == null) map[y][x] = new HashMap<>();

                    count = map[y][x].getOrDefault(turn, 0);
                    if (count == 1) {
                        result++;
                    }
                    map[y][x].put(turn, count + 1);
                }
            }
        }
        
        return result;
    }
}