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

요구사항

각자 지정된 출발 지점에서 운송 지점 까지 최단 경로로 이동하는 로봇이 있으며

이동 중 같은 좌표에 로봇이 2대 이상 모이면 위험 상황으로 판단된다.

모든 로봇이 운송을 마칠 때까지 발생하는 위험 상황의 횟수 구하기

(최단 경로가 여러가지 인 경우 r좌표 이동을 우선함)

 

 

입력 값

int[][] points	지점의 r, c 정보를 담은 2차원 배열 points[i] 는 i+1 번째 지점 정보 배열 points[i][0] 는 i+1 번째 지점의 r 좌표 points[i][1] 는 i+1 번째 지점의 c 좌표
int[][] routes	로봇의 출발 지점, 운송 지점을 담은 2차원 배열 routes[i] 는 i+1 번째 로봇의 운송 정보 배열 routes[i][j] 는 i+1 번째 로봇의 j+1 번째 운송 지점 번호 (j=0 은 출발 지점)

 

 

풀이

1. 로봇 이동경로 비교 및 저장을 위한 변수 생성

int sttPointR, sttPointC;	출발 지점 좌표
int endPointR, endPointC;	도착 지점 좌표
int sec;	시간대
Set<String> moves    = new HashSet<>();	모든 이동 좌표 (중복X) moves.get(i) 는 "시간대-r좌표-c좌표" 형태의 문자열 저장
Set<String> dupMoves = new HashSet<>();	충돌 좌표 (중복X) dupMoves.get(i) 는 "시간대-r좌표-c좌표" 형태의 문자열 저장

 

2. 모든 좌표 저장을 위해 모든 로봇의 모든 운송 지점 loop

 

3. 로봇의 출발 지점 좌표를 현재 시간과 함께 moves(이동 경로 좌표)에 저장

 

4. 로봇의 현재 좌표와 다음 좌표를 비교하여 최단 거리로 이동하며  현재 시간과 함께 moves(이동 경로 좌표)에 저장

    -> 최단 경로가 여러가지 인 경우 r좌표 이동을 우선함

 

5. 동 시간대에 같은 좌표가 이미 있다면 dupMoves(충돌 좌표)에 저장

 

6. 모든 로봇이 모든 운송 지점을 방문할때까지 반복

 

7. 충돌 좌표 갯수 return

 

 

728x90

Java 코드

import java.util.*;

class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        
        // 출발 지점 좌표
        int sttPointR, sttPointC;
        // 도착 지점 좌표
        int endPointR, endPointC;
        // 시간
        int sec;
        // 이동 좌표
        Set<String> moves    = new HashSet<>();
        // 충돌 좌표
        Set<String> dupMoves = new HashSet<>();

        // 로봇 별
        for(int i = 0; i < routes.length; i++) {
            sec = 0;
            
            // 첫 출발점 저장
            sttPointR = points[routes[i][0] - 1][0];
            sttPointC = points[routes[i][0] - 1][1];
            
            if(moves.contains(sec + "-" + sttPointR + "-" + sttPointC)) {
                dupMoves.add(sec + "-" + sttPointR + "-" + sttPointC);
            }
            moves.add(sec + "-" + sttPointR + "-" + sttPointC);
            
            for(int j = 0; j < routes[0].length - 1; j++) {
                // 출발 지점
                sttPointR = points[routes[i][j] - 1][0];
                sttPointC = points[routes[i][j] - 1][1];
                // 도착 지점
                endPointR = points[routes[i][j+1] - 1][0];
                endPointC = points[routes[i][j+1] - 1][1];

                while((sttPointR != endPointR) || (sttPointC != endPointC)) {
                    sec++;
                    
                    if(endPointR > sttPointR) { // 아래 이동
                        sttPointR += 1;
                    } else if (endPointR < sttPointR) { // 위 이동
                        sttPointR -= 1;
                    } else if(endPointC > sttPointC) { // 오른쪽 이동
                        sttPointC += 1;
                    } else if(endPointC < sttPointC) { // 왼쪽 이동
                        sttPointC -= 1;
                    }

                    if(moves.contains(sec + "-" + sttPointR + "-" + sttPointC)) {
                        dupMoves.add(sec + "-" + sttPointR + "-" + sttPointC);
                    }
                    moves.add(sec + "-" + sttPointR + "-" + sttPointC);
                }
            }
            
        }
        
        answer = dupMoves.size();
        
        return answer;
    }
}

 

 

문제 출처

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