[백준 / BOJ] 1944 복제 로봇 (Java)

문제

출처 : https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

특정한 위치에서 무한히 복제할수있는 로봇이 있다.

로봇은 미로의 출발점 'S'에서 시작해 모든 키'K'를 찾는것이 목표이다.

로봇은 'S'혹은'K'위에서 무한히 복제할수있다.

미로가 주어졌을때, 로봇이 모든 키를 찾기위해 움직여야하는 최솟값을 구하는 문제다.

 

---

풀이

MST로 푸는 문제였다. 

로봇은 시작지점과 키가있는 위치에서 무한히 복제할수있다. 즉, 키의 갯수만큼 로봇을 복제하고, 모든 키의방향으로 로봇을 보낼수있다는 뜻이다. 하지만 이 때, 하나의 로봇이 두개이상의 키를 연속해서 방문하는경우가 최소일수있으니, MST로 풀어야했다.

 

로직

1. BFS를 사용해서, 현재 위치 에서 갈수있는 모든 키들을 priorityQueue에 넣는다. (가중치값을 반드시 포함해야함)

2. PriorityQueue에 저장되어있는값중 가중치값이 가장 적은 키를 꺼낸후 더한다.

- 이때, 해당 키를 로봇이 찾았는지의 유무만 확인하면 되기 때문에, 어느 로봇이 방문했는지는 중요하지않다,

 

MST알고리즘 코드

    private int doMST(){
        int ret = 0;
        int findCount = -1; // 출입구 제거하기위해 -1로 지정
        while(!pq.isEmpty()){
            int nowY = pq.peek().y;
            int nowX = pq.peek().x;
            int nowWeight = pq.peek().weight;
            pq.poll();
            if(!check[nowY][nowX]) continue;
            check[nowY][nowX] = false;
            ret += nowWeight;
            findCount++;
            setWeight(nowY, nowX);
        }
        if(findCount < M) return -1;
        return ret;
    }

setWeight는 하나의 키를 선택할때마다 해당 키와 다른 키들의 가중치값을 업데이트 해주는 함수다.(코드는 아래 링크에 있다.)

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1944%20%EB%B3%B5%EC%A0%9C%20%EB%A1%9C%EB%B4%87/Main.java

devxb/JJUNalgo