[PCCP 기출 3번] 충돌위험 찾기

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

프로그래머스

 

 

 

 

문제유형

• 구현

문제 난이도

• Lev2

 

문제 분석

- x개의 로봇에 대해서 각자 도착해야하는 포인트 지점들이 주어진다.
- 모든 로봇은 한 번에 한 칸씩만 움직일 수 있고, 자신이 도착해야하는 포인트들을 모두 거치면 종료된다.
- 이때, 로봇끼리 만나는 경우를 충돌 위험 상황이라고 판단하고, 충돌 횟수를 구하는 문제이다. 만약, 같은 시간에 여러 개의 충돌이 일어난다면 모든 충돌을 각각 카운팅한다.
- 최단 경로가 여러 개 존재할 경우, X좌표를 먼저 움직이는 경우를 우선한다.

 

시행 착오

우선 각 좌표들은 <= 100 이하였고, 로봇으 개수도 최대 100개였다. 처음에 생각했을 땐, 이동할 수 있는 방향이 로봇마다 최대 4개의 방향이고, X좌표를 먼저 이동한다 치더라도, 한 번의 이동에 4^100번씩 필요하므로 시간 초과를 어떻게 줄여야 할지 막막했다.
그래서 살짝 힌트를 활용했고, 우선 X좌표를 포인트지점과 일치시킨 이후, Y좌표를 이동시키면 되겠다라는 생각이 들었다.

내가 논리적으로 변수 이름과 논리적인 순서로 문제를 풀지 않다보니, 중간에 좌표간의 이동과 충돌 횟수를 구하는 과정에서 로직이 꼬였다..
프로그래머스에서 직접 풀 때는 평소보다 눈에도 코드가 안들어오고, 크기가 작으므로, 항상 논리적으로 변수명을 정해서 기억해야 할 것이고, 반복되는 부분은 메소드로 따로 빼서 공통적인 부분에서 실수를 하지 않도록 줄여야겠다.

 

코드 분석

우선 로봇의 위치와, 인덱스, 다음 이동할 운송 지점을 instance에 담기 위해 객체를 생성하였다.

static class Node {
        int idx, next, x, y;
        
        public Node(int idx, int next, int x, int y) {
            this.idx = idx;
            this.next = next;
            this.x = x;
            this.y = y;
        }
    }

 

문제에서 input으로 주어지는 포인트의 위치들을 통해 해당 위치에 최댓값, 최솟값의 X좌표와 Y좌표를 로봇이 넘어가면 최단 경로가 되지 않을 것이기 때문에 boundary를 메소드로 만들었지만, 굳이 하지 않아도 괜찮다. 왜냐면 초기에 해당 메소드를 작성했을 때에는 모든 방향에 대해 좌표를 저장해야하나 고민하면서, 최대한 시간 초과를 줄이기 위해 해당 메소드를 작성한 것이다.

static void checkBound(int[][] points, int n) {
        
        for(int i = 0; i < n; i++) {
            if(points[i][0] > x2) x2 = points[i][0];
            if(points[i][0] < x1) x1 = points[i][0];
            
            if(points[i][1] > y2) y2 = points[i][1];
            if(points[i][1] < y1) y1 = points[i][1];
        }
        
    }

 

다음 코드는 모든 로봇들을 한 칸씩 움직이기 위한 메소드이다.

코드에서 중요한 점은 Queue의 활용과 visited 방문 배열 처리이다.

만약, 로봇이 경유해야 하는 모든 운송 경로를 도착한 경우, 더이상 queue에 삽입하지 않아도 되므로 방문 처리하였다.

 

한 번 이동할 때마다, 모든 로봇들을 queue에 넣어두고, 각자 한 칸씩 이동한 후, instance에 현재 위치 좌표와 다음 이동할 운송 idx를 수정해줬다.

이동할 우선순위는 X좌표가 먼저 움직이기 때문에 다음과 같이 조건문을 분기 처리했다. 해당 부분에서 실수를 했기 때문에 주의해야할 것 같다.

static void move(int[][] points, int[][] routes) {
        
        ArrayDeque<Node> q = new ArrayDeque<>();
        
        while(true) {

            for(int i = 1; i <= x; i++) {
                // 아직 최종 목적지까지 도달하지 않은 경우, queue에 삽입
                if(!visited[i]) {
                    q.offer(nodes[i]);
                }
            }
            
            // 더이상 탐색해야할 로봇이 없는 경우
            if(q.size() == 0) break;
            
            while(!q.isEmpty()) {
            
                Node p = q.poll();
            
                // 다음 point가 없는 경우
                if(p.next == m) {
                    // visited[p.idx] = true;
                    continue; // 가야할 모든 경로를 도착한 로봇팔
                }
            
                int idx = p.idx;
                int next = routes[idx - 1][p.next]; // 이동해야할 포인트
            
                // 이동할 위치의 포인트
                int nx = points[next - 1][0];
                int ny = points[next - 1][1];
                
                if (nodes[idx].x != nx) {
                    if (nodes[idx].x < nx) {
                        nodes[idx].x++;
                    } else {
                        nodes[idx].x--;
                    }
                } else if (nodes[idx].y != ny) {
                    if (nodes[idx].y < ny) {
                        nodes[idx].y++;
                    } else {
                        nodes[idx].y--;
                    }
                }

                // 도착 여부 판단
                if (nodes[idx].x == nx && nodes[idx].y == ny) {
                    nodes[idx].next++;
                }
            }
            
            for(int i = 1; i <= x; i++) {
                if(!visited[i]) arr[nodes[i].x][nodes[i].y]++;
            }
            
            res += touch();
            
            for(int i = 1; i <= x; i++) {
                if(nodes[i].next == m && !visited[i]) {
                    visited[i] = true;
                }
            }           
        }   
    }

 

 

다음 코드는 충돌 횟수를 찾는 메서드이다.

보면 알겠지만, 이전에 move() 메서드에서 방문하지 않은 로봇의 위치에 대해서 arr 배열에 counting을 해주고, 해당 counting이 2개 이상일 경우, 충돌한 것이므로 counting++해주었다.

 

해당 메서드 부분은 더 최적화가 가능할 것 같은데, 난 단순하게 배열을 통해 counting 해주었다.

static int touch() {
        int count = 0;
        
        for(int i = 0; i <= x2; i++) {
            for(int j = 0; j <= y2; j++) {
                if(arr[i][j] > 1) {
                    count++;
                }
            }
        }
        
        for(int i = 0; i <= x2; i++) Arrays.fill(arr[i], 0);

        return count;
    }

 

 

전체 코드

다음은 전체 코드이다.

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

class Solution {
    static class Node {
        int idx, next, x, y;
        
        public Node(int idx, int next, int x, int y) {
            this.idx = idx;
            this.next = next;
            this.x = x;
            this.y = y;
        }
    }
    
    static void checkBound(int[][] points, int n) {
        
        for(int i = 0; i < n; i++) {
            if(points[i][0] > x2) x2 = points[i][0];
            if(points[i][0] < x1) x1 = points[i][0];
            
            if(points[i][1] > y2) y2 = points[i][1];
            if(points[i][1] < y1) y1 = points[i][1];
        }
        
    }
    
    static void move(int[][] points, int[][] routes) {
        
        ArrayDeque<Node> q = new ArrayDeque<>();
        
        while(true) {

            for(int i = 1; i <= x; i++) {
                // 아직 최종 목적지까지 도달하지 않은 경우, queue에 삽입
                if(!visited[i]) {
                    q.offer(nodes[i]);
                }
            }
            
            // 더이상 탐색해야할 로봇이 없는 경우
            if(q.size() == 0) break;
            
            while(!q.isEmpty()) {
            
                Node p = q.poll();
            
                // 다음 point가 없는 경우
                if(p.next == m) {
                    // visited[p.idx] = true;
                    continue; // 가야할 모든 경로를 도착한 로봇팔
                }
            
                int idx = p.idx;
                int next = routes[idx - 1][p.next]; // 이동해야할 포인트
            
                // 이동할 위치의 포인트
                int nx = points[next - 1][0];
                int ny = points[next - 1][1];
                
                if (nodes[idx].x != nx) {
                    if (nodes[idx].x < nx) {
                        nodes[idx].x++;
                    } else {
                        nodes[idx].x--;
                    }
                } else if (nodes[idx].y != ny) {
                    if (nodes[idx].y < ny) {
                        nodes[idx].y++;
                    } else {
                        nodes[idx].y--;
                    }
                }

                // 도착 여부 판단
                if (nodes[idx].x == nx && nodes[idx].y == ny) {
                    nodes[idx].next++;
                }
            }
            
            for(int i = 1; i <= x; i++) {
                if(!visited[i]) arr[nodes[i].x][nodes[i].y]++;
            }
            
            res += touch();
            
            for(int i = 1; i <= x; i++) {
                if(nodes[i].next == m && !visited[i]) {
                    visited[i] = true;
                }
            }           
        }   
    }
    
    static int touch() {
        int count = 0;
        
        for(int i = 0; i <= x2; i++) {
            for(int j = 0; j <= y2; j++) {
                if(arr[i][j] > 1) {
                    count++;
                }
            }
        }
        
        for(int i = 0; i <= x2; i++) Arrays.fill(arr[i], 0);

        return count;
    }
    
    static int x, n, m;
    static int res = 0;
    static int[][] arr;
    static Node[] nodes;
    static int x1 = 101, x2 = -1, y1 = 101, y2 = -1;
    static boolean[] visited;
    public int solution(int[][] points, int[][] routes) {
        x = routes.length; // 로봇의 개수 
        n = points.length; // 포인트의 개수
        m = routes[0].length; // 경로의 개수
        visited = new boolean[x+1];
        
        nodes = new Node[x + 1];
        
        for(int i = 1; i < x + 1; i++) {
            int idx = routes[i - 1][0];
            
            nodes[i] = new Node(i, 0, points[idx-1][0], points[idx-1][1]);
        }
        
        checkBound(points, n);
                
        arr = new int[x2+2][y2+2];
        move(points, routes);
        
        return res;
    }
}