복제로봇 [백준 1944][JAVA][골드 2][BFS][MST][Prim]

 

[광고 누르면 오늘의 행운 상승!!]

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

1944번: 복제 로봇

2가지 방법으로 풀었다.

1. MST(Prim)를 이용한 방법
- 메모리 52768KB 시간 280ms

- 맵을 숫자 배열로 변환한다
- bfs를 통해 맵과 키들을 간선으로 이어준다.
- 만들어진 그래프를 Prim 알고리즘 (우선순위 큐를 이용 했다 ) 을 이용하여 가장 최단 경로를 뽑아내었다.
- 모든 키를 회수할 수 있으면 거리를, 없다면 -1를 출력하였다.

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

public class Main {

	static class Robot implements Comparable<Robot>{
		int node;
		int dis;
		
		public Robot(int node, int dis) {
			this.node = node;
			this.dis = dis;
		}

		@Override
		public int compareTo(Robot o) {
			return Integer.compare(this.dis, o.dis);
		}
	}
	
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int[][] map;
	static boolean[][] visit;
	static boolean flag;
	static int N,KEY,cnt=1,dis;
	static PriorityQueue<Robot> pq = new PriorityQueue<>();
	static Queue<int[]> q = new LinkedList<>();
	static ArrayList<ArrayList<Robot>> graph;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		KEY = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				if(ch[j] == '1') map[i][j] = -2;
				if(ch[j] == '0') map[i][j] = -1;
				if(ch[j] == 'S' || ch[j] == 'K') {
					if(ch[j] == 'S') {
						map[i][j] = 0;
					}else {
						map[i][j] = cnt++;
					}
					q.add(new int[] {i,j});
				}
			}
		}
		
		//그래프 초기화
		graph = new ArrayList<>();
		for (int i = 0; i < q.size(); i++) {
			graph.add(new ArrayList<>());
		}
		
		//간선 생성
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			bfs(pos[0], pos[1]);
		}
		
		if(Prim()) System.out.println(dis);
		else	   System.out.println(-1);
	}

	private static boolean Prim() {
		boolean[] visit = new boolean[KEY+1];
		int cnt = 0;
		pq.add(new Robot(0,0));
		
		while(!pq.isEmpty()) {
			Robot robot = pq.poll();
			
			//방문했으면 continue
			if(visit[robot.node]) continue;
			visit[robot.node] = true;
			dis+= robot.dis;
			
			if(++cnt == KEY+1) { 
				return true;
			}
				
			//정점과 연결된 모든 정점을 순회
			for(Robot next : graph.get(robot.node)) {
				pq.add(next);
			}
		}
		return false;
	}

	private static void bfs(int row, int col) {
		Queue<int[]> q = new LinkedList<>();
		visit = new boolean[N][N];
		q.add(new int[] {row,col,0});
		
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = pos[0] + dx[i];
				int ny = pos[1] + dy[i];
				
				//맵밖
				if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
				//방문
				if(visit[nx][ny]) continue; 
				//벽
				if(map[nx][ny] == -2) continue;
				//key를 발견했을 때
				if(map[nx][ny] > 0) {
					graph.get(map[row][col]).add(new Robot(map[nx][ny],pos[2]+1));
				}
				//방문처리
				visit[nx][ny] = true;
				q.add(new int[] {nx,ny,pos[2]+1});
			}
		}
	}
}

2. 거리를 갱신시키는 BFS , 우선순위 큐 이용
- 메모리 14772KB 시간 124ms

- 맵을 전부 Integer.MaxValue로 채워놓는다.
- 맵을 숫자 배열로 변환한다 (시작점과 키 모두 0으로 변환한다.)
- pq에 시작점을 담고 bfs를 시작하는데 이동할 때 이동할 곳이 내가 이동해온 거리보다 적다면 갱신시킨다.
- key의 위치를 q에 담는다.
- 키를 만나면 거리를 0으로 초기화 하여 다시 pq에 담는다(복제) 
- 반복하다가 pq가 종료되면 key의 위치를 담은 q를 poll()하면서 key의 위치에 담긴 숫자(갱신된 거리)를 더한다
- 키의 갯수(M)가 cnt와 같다면 답을 출력하고 아니라면 -1를 출력한다.

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

public class Main {

	static class Robot implements Comparable<Robot> {
		int row, col;
		int dis;

		public Robot(int row, int col, int dis) {
			this.row = row;
			this.col = col;
			this.dis = dis;
		}

		@Override
		public int compareTo(Robot o) {
			return this.dis - o.dis;
		}

	}
	static int dx[] = { 1, 0, -1, 0 };
	static int dy[] = { 0, -1, 0, 1 };
	
	static int N, M,res, cnt;
	static int SROW, SCOL;
	
	static int map[][];
	static boolean visit[][];
	
	static Queue<int[]> q = new LinkedList<>();
	static PriorityQueue<Robot> pq = new PriorityQueue<>();

	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visit = new boolean[N][N];
		map = new int[N][N];
		
		for (int i = 0; i < N; i++)
			Arrays.fill(map[i], Integer.MAX_VALUE);

		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < N; j++) {
				char c = s.charAt(j);
				if (c == '1') {
					map[i][j] = -1;
					continue;
				}
				
				if (c == 'S') {
					pq.add(new Robot(i, j, 0));
					visit[i][j] = true;
				}else if (c == 'K') { 
					//key 자리를 0
					q.add(new int[] {i,j});
					map[i][j] = 0;
				}
			}
		}

		bfs();
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			res+= map[pos[0]][pos[1]];
		}
		
		if(cnt == M)
			System.out.println(res);
		else
			System.out.println(-1);
		
	}

	private static void bfs() {
		while (!pq.isEmpty()) {
		
			Robot robot = pq.poll();
			//현재 자리가 키라면 로봇 복제
			if (map[robot.row][robot.col] == 0) {
				map[robot.row][robot.col] = robot.dis;
				cnt++;
				if (cnt == M)
					return;
				//거리를 초기화한 로봇
				pq.add(new Robot(robot.row, robot.col, 0));
				continue;
			}
			for (int d = 0; d < 4; d++) {
				int nx = robot.row + dx[d];
				int ny = robot.col + dy[d];
				if (!safe(nx, ny) || map[nx][ny] == -1) continue;
				
				//키라면
				if (map[nx][ny] == 0) {
					visit[nx][ny] = true;
					pq.add(new Robot(nx, ny, robot.dis + 1));
				}
				//더 빠른 경로로 이동할 수 있다면
				else if (robot.dis + 1 < map[nx][ny] && !visit[nx][ny]) {
					//맵 갱신
					map[nx][ny] = robot.dis + 1;
					pq.add(new Robot(nx, ny, robot.dis + 1));
				}
			}
		}
	}

	private static boolean safe(int nx, int ny) {
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
			return true;
		return false;
	}

}