[PS][PCCP 기출문제] 3번 / 충돌위험 찾기 java 풀이 (+조건문 없음, 64 lines)

코딩테스트 연습 - [PCCP 기출문제] 3번 / 충돌위험 찾기 | 프로그래머스 스쿨

프로그래머스

처음 문제 풀이

대충 중간에 하다가 영 아닌 것 같아서 포기한 코드

import java.util.*;

class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        
        Queue<Point> queue = new ArrayDeque<>();
        for (int [] route : routes) {
            Point point = new Point(points[route[0] - 1][0], points[route[0] - 1][1], points[route[1] - 1], points[route[1] - 1]);
            queue.offer(point);
        }
        
        while (!queue.isEmpty()) {
            Point currentPoint = queue.poll();
            boolean[] isVisited = new boolean[routes.length];
            if (currentPoint.row > currentPoint.targetRow) {
                currentPoint.row -= 1;
                queue.offer(currentPoint);
                continue;
            }
            if ()
            
        }
        
        
        return answer;
    }
}

• Point에는 현재 좌표, 가야하는 좌표를 저장한다.
• Queue에 Point를 넣는다.
• 하나씩 Point를 꺼내면서 row 부터 움직이고, 그때마다 isVisited에 표시하면서 다음 queue에서 Point를 꺼낼 때 방문 표시가 되어있으면 충돌 횟수를 + 1
• 근데 이렇게 구현하면 시간의 흐름에 따라 움직이는게 아니게 된다.

시간의 흐름을 시뮬레이션해야 한다. 각 시간 단위마다 모든 로봇을 규칙에 따라 움직이고, 그 시간에 충돌 위험이 있는지 확인해야 한다.

chatGPT o1 preview의 풀이

1. 해시맵 선언

int n = points.length;
int x = routes.length; // 로봇의 수
Map<String, Integer> positionCount = new HashMap<>();

Map<Integer, int[]> pointMap = new HashMap<>();
for (int i = 0; i < n; i++) {
    pointMap.put(i + 1, points[i]);
}

• positionCount는 <"time-row-col", 방문 횟수> 를 저장하는 해시맵이다. 예를 들어, 2번째 턴에서 [3,4] 좌표에 처음 로봇이 방문했다면 <"2-3-4", 1>가 저장될 것이며, 이후에 key를 다시 방문했을 때는 <"2-3-4", 2> 일 것이다.
• pointMap은 <포인트 번호, 포인트 좌표>로 저장될 해시맵이다. 예를 들어,[[3, 2], [6, 4], [4, 7], [1, 4]] 에서는 <1,[3,2]> 가 저장된다.

2. 각 로봇 별로 순회하며 위 해시맵 업데이트

 for (int robot = 0; robot < x; robot++) {
            int time = 0;
            int[] currentPos = pointMap.get(routes[robot][0]); // 로봇의 출발 포인트 번호로 현재 위치를 pointMap에서 찾음

• time = 0으로 초기화 하고, currentPos는 routes[robot][0]은 현재 로봇의 첫 시작 포인트 번호이며 이를 pointMap에서 실제 좌표를 가져온다

3. 행 먼저 목표 좌표 행까지 이동하고, positionCount에 <key, count> 삽입

 // 현재 로봇이 방문해야 하는 포인트 지점 개수만큼 순회, i = 1부터 해야 다음 지점부터 시작
for (int i = 1; i < routes[robot].length; i++) {
    int[] nextPos = pointMap.get(routes[robot][i]);

    int curRow = currentPos[0];
    int nextRow = nextPos[0];
    int col = currentPos[1];

    int rStep = (curRow < nextRow) ? 1 : -1; // 목표 행 위치가 더 크면 +1로 가야하고, 아니면 -1로 가야하므로
    while (curRow != nextRow) { // 행이 같아질 때 까지 이동
        String key = time + "-" + curRow + "-" + col;
        positionCount.put(key, positionCount.getOrDefault(key, 0) + 1); // 현재 시간과 위치에 따른, 방문 횟수를 + 1
        curRow += rStep;
        time++;
    }

• i = 1부터 순회해야 다음 이동해야 하는 포인트 좌표를 가져올 수 있다.
• 현재 위치의 행이 다음 행 보다 작으면 + 1로 가야하고, 아니라면 -1로 가야하므로 이를 rStep에 저장한다.
• while 문으로 row가 같아질 때 까지 순회한다. 이 때 key는 time + "-" + 현재 행 좌표 + "-" + 현재 열 좌표, 값은 getOrDefault(key, 0) + 1로 하여 이미 있다면 기존 값에 + 1을 하고 아니면 1로 초기화한다.
• 이후 현재 행 좌표 값에 rStep을 더하고 time + 1 을 해준다.
• 결과적으로 현재 행에서 목표 행까지 가기 위한 모든 <시간+좌표, 그 때 방문 횟수>가 positionCount에 업데이트 된다.

4. 열 좌표를 이동시키면서 positionCount에 <key, count> 업데이트

int curCol = col;
int nextCol = nextPos[1];
int cStep = (curCol < nextCol) ? 1 : -1;
while (curCol != nextCol) { // 열이 같아질 때 까지 이동
    String key = time + "-" + curRow + "-" + curCol;
    positionCount.put(key, positionCount.getOrDefault(key, 0) + 1); // 현재 시간과 위치에 따른, 방문 횟수를 + 1
    curCol += cStep;
    time++;
}

currentPos = nextPos; // 현재 위치를 다음 위치로 초기화
}
// 마지막 위치 기록
String key = time + "-" + currentPos[0] + "-" + currentPos[1];
positionCount.put(key, positionCount.getOrDefault(key, 0) + 1);
}

• 행과 마찬가지의 로직을 수행한다.
• 목표 열 좌표까지 도착했다면, 현재 위치를 다음 위치로 바꾼다. 그리고 다시 for 문을 수행하면서 다음 포인트 숫자까지 가기 위한 시뮬레이션이 진행되고, positionCount에 업데이트 될 것이다.
• 목표 포인트에 도달했다면 그 위치도 positionCount에 추가한다.

5. positionCount의 value를 순회하면서 정답 값 출력

int answer = 0;
for (int count : positionCount.values()) { // 각 key 별로 기록한 방문 횟수를 순회
    if (count >= 2) {
        answer++;
    }
}

• positionCount에는 시간과 좌표 별로 방문 횟수가 기록되어 있을테니, 2번 이상 방문했다면 충돌 횟수로 감지한다.

정답 코드

import java.util.*;

public class Solution {
    public int solution(int[][] points, int[][] routes) {
        int n = points.length;
        int x = routes.length; // 로봇의 수
        Map<String, Integer> positionCount = new HashMap<>();
        
        // <포인트 번호, 그 포인트의 위치[row, col]> 
        Map<Integer, int[]> pointMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            pointMap.put(i + 1, points[i]);
        }
        
        for (int robot = 0; robot < x; robot++) {
            int time = 0;
            int[] currentPos = pointMap.get(routes[robot][0]); // 로봇의 출발 포인트 번호로 현재 위치를 pointMap에서 찾음
            
            // 현재 로봇이 방문해야 하는 포인트 지점 개수만큼 순회, i = 1부터 해야 다음 지점부터 시작
            for (int i = 1; i < routes[robot].length; i++) {
                int[] nextPos = pointMap.get(routes[robot][i]);
                
                int curRow = currentPos[0];
                int nextRow = nextPos[0];
                int col = currentPos[1];
                
                int rStep = (curRow < nextRow) ? 1 : -1; // 목표 행 위치가 더 크면 +1로 가야하고, 아니면 -1로 가야하므로
                while (curRow != nextRow) { // 행이 같아질 때 까지 이동
                    String key = time + "-" + curRow + "-" + col;
                    positionCount.put(key, positionCount.getOrDefault(key, 0) + 1); // 현재 시간과 위치에 따른, 방문 횟수를 + 1
                    curRow += rStep;
                    time++;
                }
                
                // 행 이동이 끝났다면, 이제 열 이동
                int curCol = col;
                int nextCol = nextPos[1];
                int cStep = (curCol < nextCol) ? 1 : -1;
                while (curCol != nextCol) { // 열이 같아질 때 까지 이동
                    String key = time + "-" + curRow + "-" + curCol;
                    positionCount.put(key, positionCount.getOrDefault(key, 0) + 1); // 현재 시간과 위치에 따른, 방문 횟수를 + 1
                    curCol += cStep;
                    time++;
                }
                
                currentPos = nextPos; // 현재 위치를 다음 위치로 초기화
            }
            
            // 마지막 위치 기록
            String key = time + "-" + currentPos[0] + "-" + currentPos[1];
                    positionCount.put(key, positionCount.getOrDefault(key, 0) + 1);
        }
        
        int answer = 0;
        for (int count : positionCount.values()) { // 각 key 별로 기록한 방문 횟수를 순회
            if (count >= 2) {
                answer++;
            }
        }
        
        return answer;

    }
}

 

느낀점

핵심은 key 인 것 같다... "time-행좌표-열좌표" 에 따른 방문 횟수를 모두 기록하기 위해 해시맵 자료구조를 사용하고, getOfDefault를 사용해서 초기화 하는 방법.. 

맨 처음에는 그때 그때 판별하는 방식으로 하려했어서 더 복잡해졌는데, gpt가 푼 방법은 모두 시뮬레이션을 돌린 후에 결과만 출력하니 더 깔끔한 것 같다.

구글링을 하면서 아 최단 경로로 가면서 어딘가에 다 기록해두면 되겠구나 떠올렸고, int[][] map 이런거에다가 방문 횟수를 저장하려 했는데 이것도 가능하긴 할듯..?

 

아무튼, 아이디어가 안 떠오르면 진짜 어케 푸냐..