[Programmers] PCCP 기출문제 충돌위험 찾기 (JAVA)

프로그래머스

 

풀이

 

BFS로 해결해야하는 문제일 것 같았는데,

다음 포인트로 이동할 때는 항상 최단 경로로 이동하며 최단 경로가 여러 가지일 경우, 
r 좌표가 변하는 이동을 c 좌표가 변하는 이동보다 먼저 합니다.

 

r좌표로 먼저 이동해야한다는 조건이 있었다.

 

그럼 이 경우 무조건 좌-우로 이동한 뒤에 상-하로 이동하는 것이 최단경로일 거라 생각했다.

처음에는 A좌표 ▶ B좌표로의 이동만 하는 줄 알았는데, A좌표 ▶ B좌표 ▶ C좌표 처럼 경유하는 케이스도 있으니 주의.

 

자꾸 맞는데 왜 틀리지 했는데, 내가 tmp를 움직인 횟수+x좌표+y좌표인 String으로 중복체크를 해주고 있었는데,

뚜렷하게 구분되지 않아서 숫자가 겹치는 경우가 존재했다.

"."으로 구분해주니 해결.. (허탈)

 

전체코드

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

// 최단거리지만, bfs가 아니라 계산으로 해결해보자.
class Solution {
    static HashMap<String, Integer> map = new HashMap<>();
    static String tmp = "";
    static int cnt = 0;
    public int solution(int[][] points, int[][] routes) {
        for(int i=0; i<routes.length; i++){
            cnt = 0;
            for(int j=0; j<routes[i].length-1; j++){
                int start[] = {points[routes[i][j]-1][0], points[routes[i][j]-1][1]};
                int end[] = {points[routes[i][j+1]-1][0], points[routes[i][j+1]-1][1]};
                if(j == 0){
                    tmp = tmp+"0."+start[0]+"."+start[1];   
                    if(!map.containsKey(tmp)){
                        map.put(tmp, 1);
                    }else{
                        map.put(tmp, map.get(tmp)+1);
                    }
                }
                Move(start, end, cnt);   
            }
        }
        int answer = 0;
        for(String key : map.keySet()){
            if(map.get(key) >= 2){
                answer++;
            }
        }
        return answer;
    }
    static void Move(int start[], int end[], int c){
        while(true){
            tmp = "";
            if(start[0] < end[0]){
                start[0]++;
            }else if(start[0] > end[0]){
                start[0]--;
            }else{
                if(start[1] < end[1]){
                    start[1]++;
                }else if(start[1] > end[1]){
                    start[1]--;
                }else{
                    cnt = c;
                    return;
                }
            }
            c++;
            tmp = tmp+c+"."+start[0]+"."+start[1];
            if(!map.containsKey(tmp)){
                map.put(tmp, 1);
            }else{
                map.put(tmp, map.get(tmp)+1);
            }
        }
    }
}