문제링크

최근에 백준만 풀다가 오랜만에 프로그래머스를 푸니 좀 많이 어려웠다..
백준만 풀어서 그런게 아니라 쉬운 백준만 풀어서겠지만..

풀이

빡구현 문제이기 때문에 별다른 알고리즘을 사용하지는 않았다.

풀이는 다음과 같은 과정으로 이루어진다.
1. 각 로봇의 이동경로 저장
2. 이동 경로를 시간 순서대로 탐색하며 충돌이 발생하는지 확인

1. 이동경로 저장

각 로봇의 이동경로를 기록하기 위해 정수형 배열을 저장하는 큐 배열(Queue<int[]>[] record;)를 선언하였다.

문제에서 로봇은 모두 r좌표가 변하는 이동을 c좌표가 변하는 이동보다 먼저한다고 주어졌다. 장애물이 딱히 없기 때문에 출발지부터 목적지까지 최단거리를 구하기 위한 알고리즘을 따로 사용할 필요는 없고, 출발지부터 목적지까지의 r좌표를 먼저 맞추는 이동을 하고 c좌표를 맞추는 이동을 하면 최단거리가 된다.

public static void recordRoute(int[][] points, int[][] routes) {
        for(int i = 0; i < size; i++) {
            int from = routes[i][0] - 1;   //  출발 좌표 인덱스
            int fromR = points[from][0] -1;
            int fromC = points[from][1] -1;
            
            record[i].add(new int[]{fromR, fromC});    // 출발 좌표 기록
            
            for(int j = 1; j < routes[i].length; j++){
                int to = routes[i][j] - 1; //  도착 좌표 인덱스
                int toR = points[to][0]-1;
                int toC = points[to][1]-1;
            
                while(fromR != toR) {   //  도착지의 r좌표와 같아질 때까지 
                    if(fromR < toR) {   //  현재 r좌표와 도착지의 r좌표를 비교하면서 이동
                        fromR++;
                    } else {
                        fromR--;
                    }
                    record[i].add(new int[]{fromR, fromC});    //  r좌표 이동할 때마다 기록, c좌표에 대해서는 이동하지 않으므로 출발지의 c좌표
                }
            
                while(fromC != toC) {   //  도착지의 c좌표와 같아질 때까지 
                    if(fromC < toC) {   //  현재 c좌표와 도착지의 c좌표를 비교하면서 이동
                        fromC++;
                    } else {
                        fromC--;
                    }
                    record[i].add(new int[]{fromR, fromC});    //  c좌표 이동할 때마다 기록, r좌표는 이미 도착지점의 r좌표가 되어있을 것
                }
            }
        }    
    }

처음에 문제를 제대로 안읽어서, 로봇이 하나의 출발지에서 하나의 도착지로 이동하는 줄 알고 for 문을 하나만 사용했다. 하지만 로봇은 문제의 입력예시 3번처럼, 첫번째 도착지까지 간 후 다음 도착지가 있다면 이동을 계속한다.
따라서 위 코드의 두번째 반복문(for(int j = 1; j < routes[i].length; j++))처럼 경로의 길이를 확인하고 이동을 이어가야한다.

2. 충돌위험 카운트

모든 로봇이 이동을 마치고 탈출하면 연산을 종료해야하므로 탈출로봇 개수를 카운트하기 위한 변수를 선언 및 초기화한다.

while문 내에서 escapeRobots를 0으로 초기화 시켜 매 초마다 모든 로봇의 탈출여부를 파악한다.

이동경로를 저장한 큐인 record가 비어있다면 해당 시간에 로봇이 탈출한 것이므로 escapeRobots를 증가시키고, 다음 로봇의 이동경로를 확인한다.

이동경로가 남아있는 로봇은 다음 이동할 곳을 map배열에 표시한다.

해당시간에 모든 로봇을 이동시킨 후, map 배열을 돌며 1보다 큰 값 즉, 충돌위험이 있는 좌표가 있을 경우 answer을 증가시킨다.

탈출한 로봇이 총 로봇 수와 같을 때까지 위 과정을 반복한다.

    public static void findCollision() {
        int escapeRobots = 0;   // 탈출 로봇 개수 카운트하기 위한 변수 초기화
        while(escapeRobots != size){    //  모든 로봇이 탈출할 때까지
            int[][] map = new int[101][101];
            escapeRobots = 0;   //  매초마다 탈출한 로봇 수가 총 로봇 수와 같은지 비교를 해야하므로 0으로 초기화
            for(int i = 0; i < size; i++){  //  로봇 수 만큼
                if(record[i].isEmpty()){    //  이동 경로가 비어있다면 로봇이 탈출한 것임
                    escapeRobots++; 
                    continue;
                }
                int[] temp = record[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){    //  특정 위치에 1보다 큰 수가 저장되어 있다는 것은 한 대 이상의 로봇이 위치해있다는 것
                        answer ++;
                    }
                }
            }
        }
        
    }

코드

import java.io.*;
import java.util.*;

class Solution {
    static Queue<int[]>[] record;
    static int answer = 0;
    static int size;
    
    public int solution(int[][] points, int[][] routes) {
        size = routes.length;
        record = new LinkedList[size];
        for(int i = 0;i<size;i++){
            record[i] = new LinkedList<>();
        }
        recordRoute(points, routes);
        findCollision();

        return answer;
    }
    
    public static void findCollision() {
        int escapeRobots = 0;   // 탈출 로봇 개수 카운트하기 위한 변수 초기화
        while(escapeRobots != size){    //  모든 로봇이 탈출할 때까지
            int[][] map = new int[101][101];
            escapeRobots = 0;   //  매초마다 탈출한 로봇 수가 총 로봇 수와 같은지 비교를 해야하므로 0으로 초기화
            for(int i = 0; i < size; i++){  //  로봇 수 만큼
                if(record[i].isEmpty()){    //  이동 경로가 비어있다면 로봇이 탈출한 것임
                    escapeRobots++; 
                    continue;
                }
                int[] temp = record[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){    //  특정 위치에 1보다 큰 수가 저장되어 있다는 것은 한 대 이상의 로봇이 위치해있다는 것
                        answer ++;
                    }
                }
            }
        }
        
    }
    
    public static void recordRoute(int[][] points, int[][] routes) {
        for(int i = 0; i < size; i++) {
            int from = routes[i][0] - 1;   //  출발 좌표 인덱스
            int fromR = points[from][0] -1;
            int fromC = points[from][1] -1;
            
            record[i].add(new int[]{fromR, fromC});    // 출발 좌표 기록
            
            for(int j = 1; j < routes[i].length; j++){
                int to = routes[i][j] - 1; //  도착 좌표 인덱스
                int toR = points[to][0]-1;
                int toC = points[to][1]-1;
            
                while(fromR != toR) {   //  도착지의 r좌표와 같아질 때까지 
                    if(fromR < toR) {   //  현재 r좌표와 도착지의 r좌표를 비교하면서 이동
                        fromR++;
                    } else {
                        fromR--;
                    }
                    record[i].add(new int[]{fromR, fromC});    //  r좌표 이동할 때마다 기록, c좌표에 대해서는 이동하지 않으므로 출발지의 c좌표
                }
            
                while(fromC != toC) {   //  도착지의 c좌표와 같아질 때까지 
                    if(fromC < toC) {   //  현재 c좌표와 도착지의 c좌표를 비교하면서 이동
                        fromC++;
                    } else {
                        fromC--;
                    }
                    record[i].add(new int[]{fromR, fromC});    //  c좌표 이동할 때마다 기록, r좌표는 이미 도착지점의 r좌표가 되어있을 것
                }
            }
        }    
    }
}