[JAVA] CodeTree 코드트리 빵

https://www.codetree.ai/training-field/frequent-problems/codetree-mon-bread/description?page=3&pageSize=20&username= 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

💡 전형적인 시뮬레이션, BFS 문제이다. → DFS는 불가능하다! 가장 먼저 도착하는 위치를 뽑아내야 되기 때문!

 

문제를 읽어보면 설명이 굉장히 친절하게 되어있다.

유의해야할 점은 1, 2, 3의 순서를 반드시 지켜야 한다는 것! 특히 2번을 조심하자!

예를 들어 M번의 사람까지 모두 이동한 다음 편의점에 접근할 수 없게 하는 것이 아니라 이동 중 3번의 사람이 편의점에 도착한다면 그때부터 해당 편의점은 접근할 수 없게 된다.

그 외에는 문제에 특별한 것은 없다. 예제가 1개이고 2번에 대한 특이점이 드러나지 않으므로 따로 생각하면서 풀어야한다.

전체 코드

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

public class Main {
	static int N, M;
	static int[][] map;
	static int[][] store;
	static boolean[][] v;
	static ArrayDeque<int[]> people;
	static int[] dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0};
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	for(int j=0; j<N; j++)
        		map[i][j] = Integer.parseInt(st.nextToken());
        }
        store = new int[M][2];
        v = new boolean[N][N];
        for(int i=0; i<M; i++){
        	st = new StringTokenizer(bf.readLine(), " ");
        	store[i][0] = Integer.parseInt(st.nextToken())-1;
        	store[i][1] = Integer.parseInt(st.nextToken())-1;
        }
        people = new ArrayDeque<>();
        int cnt = 0;
        while(true) {
        	int size = people.size();
        	if(size == 0 && cnt!=0) break;
        	while(size-- > 0) {
        		int[] t = people.poll();
        		int[] add = bfs(t[0], t[1], t[2]);
        		if(add[1] == store[t[0]][0] && add[2] == store[t[0]][1]) // 편의점 도착
        			v[add[1]][add[2]] = true;
        		else people.offer(add);
        	}
        	if(cnt < M)
        		people.offer(find_basecamp(cnt, store[cnt][0], store[cnt][1]));
        	cnt++;
        }
        System.out.println(cnt);
    }
    static int[] bfs(int n, int x, int y) {
    	ArrayDeque<int[]> q = new ArrayDeque<>();
    	q.offer(new int[] {x, y, -1, -1});
    	boolean[][] visited = new boolean[N][N];
    	visited[x][y] = true;
    	while(!q.isEmpty()) {
    		int[] now = q.poll();
    		if(now[0] == store[n][0] && now[1] == store[n][1]) {
    			return new int[] {n, now[2], now[3]};
    		}
    		for(int d=0; d<4; d++) {
    			int nx = now[0] + dx[d];
    			int ny = now[1] + dy[d];
    			if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || v[nx][ny]) continue;
    			visited[nx][ny] = true;
    			if(now[2] == -1) {
    				q.offer(new int[] {nx, ny, nx, ny});
    			}
    			else
    				q.offer(new int[] {nx, ny, now[2], now[3]});
    		}
     	}
    	return null; // number+이동한 곳의 좌표를 리턴!
    }
    static int[] find_basecamp(int n, int x, int y) { // @param : 편의점의 위치 - 가장 가까운 base camp 찾기
//    	System.out.println(x+", "+y);
    	ArrayDeque<int[]> q = new ArrayDeque<>();
    	q.offer(new int[] {x, y});
    	boolean[][] visited = new boolean[N][N];
    	visited[x][y] = true;
    	while(!q.isEmpty()) {
    		int[] now = q.poll();
    		
    		if(map[now[0]][now[1]] == 1) {
    			v[now[0]][now[1]] = true;
    			return new int[] {n, now[0], now[1]};
    		}
    		for(int d=0; d<4; d++) {
    			int nx = now[0] + dx[d];
    			int ny = now[1] + dy[d];
    			if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || v[nx][ny]) continue;
    			visited[nx][ny] = true;
    			q.offer(new int[] {nx, ny});
    		}
     	}
    	return null; // number+해당 베이스캠프의 좌표를 리턴!
    }
}

한 줄 씩 살펴보자!

static int N, M;
static int[][] map;
static int[][] store;
static boolean[][] v;
static ArrayDeque<int[]> people;
static int[] dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0};

N, M → 주어진 값

map → 주어진 지도 정보

store → 편의점 정보 (즉, store[0][0] : 1번 사람이 갈 편의점 x좌표)

v → 편의점, 베이스 캠프의 접근 여부 나타냄

people → 사람들의 현재 위치를 저장

int cnt = 0;
while(true) {
	int size = people.size();
	if(size == 0 && cnt!=0) break;
	while(size-- > 0) {
		int[] t = people.poll();
		int[] add = bfs(t[0], t[1], t[2]);
		if(add[1] == store[t[0]][0] && add[2] == store[t[0]][1]) // 편의점 도착
			v[add[1]][add[2]] = true;
		else people.offer(add);
	}
	if(cnt < M)
		people.offer(find_basecamp(cnt, store[cnt][0], store[cnt][1]));
	cnt++;
}

모두 도착하지 못하는 경우는 주어지지 않는다고 했으므로 while을 true로 둔다.

이때 조사할 사람이 0명이라면 while을 break하는데 처음 시작할 경우 당연히 0명이므로 cnt가 0일때는 제외한다.

while문을 통해 한 사람의 정보를 받아서 bfs함수를 통해 다음 위치를 조사하여 add 배열에 넣어준다. 이때 원하는 편의점에 도착했다면 v를 true로 하여 해당 위치에 접근할 수 없게 한다. 그리고 deque에 다시 넣지 않는다

편의점에 도착하지 않았다면 다시 deque에 넣어준다.

새로운 사람이 출발하는 시간을 보고 find_basecamp함수를 통해 들어갈 베이스캠프를 골라준다.

static int[] bfs(int n, int x, int y) {
	ArrayDeque<int[]> q = new ArrayDeque<>();
	q.offer(new int[] {x, y, -1, -1});
	boolean[][] visited = new boolean[N][N];
	visited[x][y] = true;
	while(!q.isEmpty()) {
		int[] now = q.poll();
		if(now[0] == store[n][0] && now[1] == store[n][1]) {
			return new int[] {n, now[2], now[3]};
		}
		for(int d=0; d<4; d++) {
			int nx = now[0] + dx[d];
			int ny = now[1] + dy[d];
			if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || v[nx][ny]) continue;
			visited[nx][ny] = true;
			if(now[2] == -1) {
				q.offer(new int[] {nx, ny, nx, ny});
			}
			else
				q.offer(new int[] {nx, ny, now[2], now[3]});
		}
 	}

현재 위치를 받아서 다음 이동할 위치를 배열로 반환하는 함수이다.

now[2], now[3]에 시작 위치를 넣어주어 마지막에도 확인할 수 있게 한다. → 이외에는 평소의 bfs와 동일하다.

4방 탐색을 통해서 도달할 수 없는 곳은 제외하고 q에 갱신된 값을 넣어 이동한다.

static int[] find_basecamp(int n, int x, int y) { // @param : 편의점의 위치 - 가장 가까운 base camp 찾기
	ArrayDeque<int[]> q = new ArrayDeque<>();
	q.offer(new int[] {x, y});
	boolean[][] visited = new boolean[N][N];
	visited[x][y] = true;
	while(!q.isEmpty()) {
		int[] now = q.poll();
		
		if(map[now[0]][now[1]] == 1) {
			v[now[0]][now[1]] = true;
			return new int[] {n, now[0], now[1]};
		}
		for(int d=0; d<4; d++) {
			int nx = now[0] + dx[d];
			int ny = now[1] + dy[d];
			if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || v[nx][ny]) continue;
			visited[nx][ny] = true;
			q.offer(new int[] {nx, ny});
		}
 	}
	return null; // number+해당 베이스캠프의 좌표를 리턴!
}

편의점에 위치를 받아서 가장 가까운 베이스캠프의 좌표를 반환하는 함수이다.

특별할 것 없는 bfs이다. 이때도 이미 방문한 편의점과 베이스캠프로 접근하는 것은 불가능 함을 유의하자