[코드트리] 코드트리 빵 JAVA 풀이 (삼성 SW 역량 기출문제)

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

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

 

 

bfs를 사용하여 최단거리를 구해서 문제를 풀었다!

사용자 위치, 베캠, 편점 리스트를 각각 따로 선언한다.

map에는 빈칸과 사용자가 지나간 적있는 베켐과 편점을 표시한다. ( 다른 사용자는 못지나가기 때문에!!)

 

bfs와 조건 처리를 잘해주고 실수가 없었다면 잘 풀 수 있는 문제였던 거 같다.. 

역시 구현은 실수를 하냐마냐가 중요한둣 ㅠㅠ 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int[] dx = { -1, 0, 0, 1 };
	static int[] dy = { 0, -1, 1, 0 };

	static int time = 0;
	static int n, m;
	static int[][] map; // 빈칸=0 , 사용한 베캠과 편점=사용자번호
	static ArrayList<Node> conv; // 편의점
	static ArrayList<Node> baseCamp; // 베캠
	static ArrayList<Node> peopleLoc; // 사용자위치

	static class Node {
		int x, y;
		boolean arrive;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

		Node(int x, int y, boolean arrive) {
			this.x = x;
			this.y = y;
			this.arrive = arrive;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		conv = new ArrayList<>();
		baseCamp = new ArrayList<>();
		peopleLoc = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				if (Integer.parseInt(st.nextToken()) == 1)
					baseCamp.add(new Node(i, j));
			}
		}

		for (int i = 1; i < m + 1; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			conv.add(new Node(x-1, y-1));
		}

		simul();

		System.out.println(time);
	}

	static void simul() {
		while (true) {
			time++;
			// 한칸씩 이동
			move();
			// 가까운 베캠에 들어가기
			if (time <= m)
				findAndGoBaseCamp();

			// 모두 편점에 도착했을 경우 종료
			if (allArrive()) {
				break;
			}
		}
	}

	static void move() {
		for (int i = 0; i < peopleLoc.size(); i++) {
			Node person = peopleLoc.get(i);
			if (person.arrive)
				continue;
			Node store = conv.get(i);

			Queue<Node> q = new LinkedList<>();
			q.add(person);
			boolean visited[][] = new boolean[n][n];
			visited[person.x][person.y] = true;
			Node[][] come = new Node[n][n];

			while (!q.isEmpty()) {
				Node node = q.poll();
				for (int j = 0; j < 4; j++) {
					int xx = node.x + dx[j];
					int yy = node.y + dy[j];

					if (xx < 0 || yy < 0 || xx >= n || yy >= n || visited[xx][yy] || (map[xx][yy] >0&&map[xx][yy]!=i+1))
						continue;

					q.add(new Node(xx, yy));
					visited[xx][yy] = true;
					come[xx][yy] = new Node(node.x, node.y);
				}
			}

			if (come[store.x][store.y] == null) {
				continue;
			}
			int cx = come[store.x][store.y].x;
			int cy = come[store.x][store.y].y;
			if (cx == person.x && cy == person.y) {
				person.x = cx;
				person.y = cy;
				store.arrive = true;
				person.arrive = true;
				map[store.x][store.y]=i+1;
				continue;
			}
			while (true) {
				int ccx = come[cx][cy].x;
				int ccy = come[cx][cy].y;
				if (ccx == person.x && ccy == person.y) {
					person.x = cx;
					person.y = cy;
					break;
				}
				cx=ccx;
				cy=ccy;
			}
		}

	}

	static void findAndGoBaseCamp() {
		Node store = conv.get(time - 1);
		int minDist = Integer.MAX_VALUE;
		int minx = 0;
		int miny = 0;
		int baseNo = 0;
		Queue<Node> q = new LinkedList<>();
		q.add(store);
		boolean visited[][] = new boolean[n][n];
		visited[store.x][store.y] = true;
		int[][] distance = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				distance[i][j]=Integer.MAX_VALUE;
			}
		}
		distance[store.x][store.y] = 0;
		while (!q.isEmpty()) {
			Node node = q.poll();
			for (int j = 0; j < 4; j++) {
				int xx = node.x + dx[j];
				int yy = node.y + dy[j];

				if (xx < 0 || yy < 0 || xx >= n || yy >= n || visited[xx][yy] || (map[xx][yy] >0&&map[xx][yy]!=time))
					continue;

				q.add(new Node(xx, yy));
				visited[xx][yy] = true;
				distance[xx][yy]=distance[node.x][node.y]+1;
			}
		}
		
		for (Node base : baseCamp) {
			if(base.arrive) continue;
			int dist=distance[base.x][base.y];
			if (minDist > dist) {
				minDist = dist;
				minx = base.x;
				miny = base.y;
				baseNo = baseCamp.indexOf(base);
			} else if (minDist == dist) {
				if (minx > base.x) {
					minDist = dist;
					minx = base.x;
					miny = base.y;
					baseNo = baseCamp.indexOf(base);
				} else if (minx == base.x && miny > base.y) {
					minDist = dist;
					minx = base.x;
					miny = base.y;
					baseNo = baseCamp.indexOf(base);
				}
			}
		}
		baseCamp.get(baseNo).arrive = true;
		peopleLoc.add(new Node(minx, miny, false));
		map[minx][miny] = time; // 사용한 베캠 표시
	}

	static boolean allArrive() {
		for (int i = 0; i < m; i++) {
			if (peopleLoc.get(i) == null || !peopleLoc.get(i).arrive)
				return false;
		}
		return true;
	}
}