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

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

프로그래머스

코딩테스트 연습 > PCCP 기출문제 > [PCCP 기출문제] 3번 / 충돌위험 찾기

 

문제 분석

난이도: LEVEL2 

문제유형: 구현/시뮬레이션 

 

문제 요구사항 요약 

각 로봇은 정해진 좌표로 움직이고 해당 좌표를 항상 최단 거리로 이동한다. 

최단 거리 경로가 여러 개인 경우 x 좌표를 우선으로 이동한다.

그리고 각 로봇들이 이동할 때 충돌하는 횟수를 기록한다. 

 

충돌 구분

ex) [1,2] 1개의 좌표에 4개의 로봇이 모이는 경우: 1번 충돌 

ex) [1,2] [3,4] 2개의 좌표에 각각 2개의 로봇이 모이는 경우: 2번 충돌 

 

즉 같은 시각, 같은 좌표에 2개 이상의 로봇이 있으면 1개의 충돌로 본다. 

같은 시각에 여러 좌표에서 여러 개의 충돌이 일어날 수 있다. 

 

static 변수 

static Queue<int[]>[] memo; // 경로 기록용 
static int size;
static int answer;

 

size = 로봇의 개수 

answer = 총 충돌 횟수

memo = 각 로봇의 이동 경로를 기억하기 위한 큐(Queue)

 

size, memo 초기화

public int solution(int[][] points, int[][] routes) {
    size = routes.length;
    memo = new LinkedList[size];
    for(int i = 0; i < size; i++){
        memo[i] = new LinkedList<>();
    }
    function(points, routes); // 경로 계산 
    function2(); // 충돌 계산 
    return answer;      
}

 

function 메소드 (아래 정답 코드 참고)

각 로봇의 이동 경로를 memo에 저장하는 메소드이다.

처음에는 BFS를 통해서 최단 경로를 구하려고 했으나 매번 BFS 경로를 하는게 의미가 있을까?

BFS를 사용해서 최단 경로를 구한다고 해도 규칙4(x좌표가 y좌표보다 우선시된다.)는 어떻게 적용할까?

이런 의문점이 들었는데 애초에 벽 같은 장애물도 없는데 그냥 x좌표 y좌표 순서대로 움직이면 된다는 아이디어가 떠올랐다.

그래서 다음 좌표 빼기 현재 좌표를 통해서 x 좌표 먼저 움직이고 y 좌표를 움직이도록 하였다. 

 

function2 메소드 (아래 정답 코드 참고)

모든 큐가 빌 때 까지 돌아간다. 

시간 개념은 그냥 큐에서 한번 뺄 때 모두 같은 시간일 테니까 해당 개념을 적용했다. 

매번 for문을 돌면서 모든 큐가 비어서 count가 로봇 개수와 같아지면 멈춘다.

 

충돌 계산

큐에서 이동한 좌표를 꺼내서 2차원 배열 map에 더해준다.

for문이 끝나고 map을 탐색하면서 만약 map에 2이상인 숫자가 있으면 충돌하였으니 answer에 추가한다.  

 

정답 코드 

import java.util.*;
class Solution {
    static Queue<int[]>[] memo; // 경로 기록용 
    static int size;
    static int answer;
    public int solution(int[][] points, int[][] routes) {
        size = routes.length;
        memo = new LinkedList[size];
        for(int i = 0; i < size; i++){
            memo[i] = new LinkedList<>();
        }
        function(points, routes); // 경로 계산 
        function2(); // 충돌 계산 
        return answer;      
    }
    public static void function2(){
        int count = 0;
        while(count != size){
            int [][] map = new int [101][101];
            count = 0;
            for(int i = 0; i < size; i++){
                if(memo[i].isEmpty()){
                    count++;
                    continue;
                }
                int [] temp = memo[i].poll();
                map[temp[0]][temp[1]]++;
            }
            for(int i = 0; i < 101; i++){
                for(int j = 0; j < 101; j++){
                    if(map[i][j] > 1) answer++; // 충돌!
                }
            }
        }
    }
    // 규칙4: 이동 우선순위 x좌표 > y좌표 
    public static void function(int [][] points, int [][] routes){
        for(int i = 0; i < size; i++){
            int [] point = points[routes[i][0] - 1];
            int x = point[0];
            int y = point[1];
            memo[i].add(new int[]{x, y});
            for(int j = 1; j < routes[0].length; j++){
                int [] next_point = points[routes[i][j] - 1];
                int nx = next_point[0];
                int ny = next_point[1];
                
                int xp = nx - x; // 다음 포인트로 이동해야하는 x좌표 
                int yp = ny - y; // 다음 포인트로 이동해야하는 y좌표
                while(xp != 0){
                    if(xp > 0){
                        xp--;
                        x++;
                        memo[i].add(new int[]{x, y});
                    }
                    else{
                        xp++;
                        x--;
                        memo[i].add(new int[]{x, y});
                    }
                }
                while(yp != 0){
                    if(yp > 0){
                        yp--;
                        y++;
                        memo[i].add(new int[]{x, y});
                    }
                    else{
                        yp++;
                        y--;
                        memo[i].add(new int[]{x, y});
                    }
                }
            }
        }
    }
}