[프로그래머스] [PCCP 기출문제] 3번 / 충돌위험 찾기 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/340211

프로그래머스

 

---

 

문제 개요

각 로봇은 정해진 경로에 따라 여러 포인트를 순서대로 방문하며, 로봇이 이동하는 과정에서 특정 좌표에서 충돌할 위험이 있을 수 있다. 이 문제의 목표는 모든 로봇이 운송을 마칠 때까지 발생하는 충돌 위험 상황의 횟수를 계산하는 것

접근 방법

1. 경로 관리 및 충돌 체크: 로봇들이 이동하는 동안 좌표에서 충돌이 발생하는지 확인해야 한다. 이를 위해 각 시간대에 로봇들이 어떤 좌표에 있는지 추적하고, 동시에 여러 로봇이 같은 좌표에 있을 때 충돌을 감지한다.
2. 좌표 이동 로직 구현:
   • 각 로봇은 두 좌표 간 최단 경로로 이동합니다. 이때 r 좌표의 변화를 우선으로 하고, 그 후에 c 좌표를 이동
   • 각 로봇이 경로의 모든 포인트를 순서대로 방문할 수 있도록 이동을 시뮬레이션
3. 충돌 위험 상황 계산: 이동 중 두 대 이상의 로봇이 동일한 좌표에 모이면 충돌 위험이 발생하는데, 이러한 충돌 위험이 발생하는 횟수를 카운트합니다.

해결 과정

1. 포인트 및 경로 설정: 주어진 포인트 정보와 로봇 경로를 기반으로 좌표를 설정하고, 각 로봇의 초기 위치와 경로를 관리한다.
2. 시뮬레이션: 모든 로봇이 동시에 출발하고, 1초마다 한 칸씩 이동하는 시뮬레이션을 진행한다. 이동할 때마다 각 로봇이 현재 위치를 기록하고, 해당 위치에서 충돌 위험이 있는지 확인한다.
3. 최종 계산: 모든 로봇이 운송을 마칠 때까지 충돌 위험 횟수를 계산한 후 반환한다.

import java.util.*;
public class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        int[][] intArrays = new int[101][101]; 

        List<Robot> list = new ArrayList<>();
        for (int i = 0; i < routes.length; i++) {
            int index = routes[i][0] - 1;
            Pos pos = new Pos(points[index][0], points[index][1]);
            Robot robot = new Robot(pos);

            intArrays[pos.y][pos.x]++;

            for (int j = 1; j < routes[i].length; j++) {
                index = routes[i][j] - 1;
                pos = new Pos(points[index][0], points[index][1]);
                robot.posList.add(pos);
            }

            list.add(robot);
        }

        for (int[] row : intArrays) {
            for (int val : row) {
                if (val > 1) {
                    answer++;
                }
            }
        }

        while (list.size() > 1) {
            List<Integer> removeList = new ArrayList<>();
            for (int i = list.size() - 1; i >= 0; i--) {
                boolean b = list.get(i).movePos(intArrays);

                if (!b) {
                    removeList.add(i);
                }
            }

            for (int idx : removeList) {
                list.remove(idx);
            }

            for (int[] row : intArrays) {
                for (int val : row) {
                    if (val > 1) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }

    public static class Robot {
        public Pos pos;
        public List<Pos> posList;

        public Robot(Pos pos) {
            this.pos = pos;
            posList = new ArrayList<>();
        }

        public boolean movePos(int[][] intArrays) {
            if (posList.size() > 0 && posList.get(0).y == pos.y && posList.get(0).x == pos.x) {
                posList.remove(0);
            }

            intArrays[pos.y][pos.x]--;

            if (posList.size() == 0) {
                return false;
            }

            if (posList.get(0).y != pos.y) {
                if (posList.get(0).y > pos.y) {
                    pos.y++;
                } else {
                    pos.y--;
                }
            } else if (posList.get(0).x != pos.x) {
                if (posList.get(0).x > pos.x) {
                    pos.x++;
                } else {
                    pos.x--;
                }
            }

            intArrays[pos.y][pos.x]++;
            return true;
        }
    }
    
    public static class Pos {
        public int y, x;

        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}