[코드트리: Java] 코드트리 빵

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread?&utm_source=clipboard&utm_medium=text

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

으레 구현문제가 그렇듯이, 아이디어를 떠올리냐 못하냐의 싸움인 거 같습니다.

 

베이스캠프를 선정하는 방법을 떠올리지 못하면 그저 어려운 문제가 되는데, 방법을 떠올리는 순간 간단하게 풀 수 있습니다.

 

또한 해당 아이디어가 특출 난 것이 아니라 매우 간단한 것이라, 사람에 따라 허탈할 수도 있다고 생각합니다.

 

해당 문제는 BFS면 다 해결되는 사실상 그래프 탐색 문제입니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m;
	static int[][] map;
	static int y, x;
	static boolean[] arrive;
	static Pos[] people;
	static Pos[] stores;
	static int time = 0;
	static int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
	
	static class Pos {
		int y, x;
		
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		arrive = new boolean[m + 1];
		people = new Pos[m + 1];
		stores = new Pos[m + 1];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken()) - 1;
			x = Integer.parseInt(st.nextToken()) - 1;
			stores[i] = new Pos(y, x);
			people[i] = new Pos(-1, -1);
		}
		
		solve();
	}

arrive: 편의점 도착여부를 확인하기 위한 배열

people: 사람들의 위치를 관리할 배열

stores: 편의점의 위치를 관리할 배열

time: 문제에서 제시한 정답

Pos: 위치 관리에 사용할 클래스

 

시간이 1분부터 돌아가기 시작할 때, 그 시간에 해당하는 사람이 움직이므로 사람들과 편의점의 위치를 관리하는 배열의 크기를 M + 1로 지정하였습니다.

 

또한 편의점의 위치를 받을 때, -1을 해줌으로써 0번 인덱스부터 시작하도록 보정했고, 사람들이 격자 밖에 있는 것을 표현하기 위해 [-1, -1]로 초기화하였습니다.

---

[풀이]

	static void solve() {
		while(!check_terminate()) {
			time += 1;
			for(int i = 1; i <= m; i++) {
				if(arrive[i] || people[i].y == -1 && people[i].x == -1) {  // 편의점에 도착했거나, 아직 베이스켐프가 아니라면
					continue;
				}
				go_store(i);
			}
			update_info();  // 모든 사람들의 이동이 끝났을 때, 편의점을 막을지 말지 확인해야 함
			if(time <= m) {  // 사람들을 베이스캠프로
				find_base(time);
			}
		}

		System.out.println(time);
	}

시뮬레이션은 모든 사람이 편의점에 도착하면 종료되도록 합니다.

1. 시뮬레이션 시작
2. 모든 사람이 도착했는지 확인
3. 시간 갱신
4. 베이스캠프 이동
5. 편의점으로 이동
   • 사람들을 확인하며 도착했거나 아직 베이스캠프에 도착하지 않은 사람들을 제외하고 
6. 모든 사람의 이동이 끝나고 이동 정보 반영

시뮬레이션의 흐름은 위와 같습니다.

 

코드의 순서는 위와 다릅니다. 이유는 처리 흐름에 있습니다.

 

만약 베이스캠프의 이동을 먼저 수행하게 되면, 코드의 흐름상 편의점 이동까지 함께 일어나게 됩니다. 왜냐하면 베이스캠프로 이동시킨 순간부터 격자밖에 있는 것이 아니기 때문에, 편의점 이동 조건에 부합하기 때문입니다.

 

이를 방지하고자 코드에서는 둘의 실행 순서를 거꾸로 위치시킵니다. 그렇게 하면 베이스캠프 이동과 편의점 이동을 동시에 처리할 수 있습니다.

 

사람들의 편의점으로의 이동이 끝났다면, 위치 정보를 갱신합니다.

 

모든 이동이 끝나고 위치를 갱신하는 이유는 편의점 도착시 접근을 막기 위함인데, 문제에서는 편의점에 도착하더라도 모든 사람들의 이동이 끝날 때까지 접근을 막을 수 없다고 명시되어 있습니다. 이를 위해 위와 같이 구현하게 되었습니다.

	static int[][] connect_road(int i) {
		Pos store = stores[i];
		int[][] visited = new int[n][n];
		visited[store.y][store.x] = 1;
		ArrayDeque<Pos> dq = new ArrayDeque<>();
		dq.add(store);
		
		while(!dq.isEmpty()) {
			Pos current = dq.poll();
			for(int[] d: directions) {
				int my = current.y + d[0], mx = current.x + d[1];
				if(0 <= my && my < n && 0 <= mx && mx < n && visited[my][mx] == 0 && map[my][mx] != -1) {
					visited[my][mx] = visited[current.y][current.x] + 1;
					dq.add(new Pos(my, mx));
				}
			}
		}
		
		return visited;
	}

편의점 기준으로  각 칸까지 가는데 어느정도 거리가 되는지 계산합니다.

 

이때 계산된 정보를 바탕으로, 베이스캠프를 선정하고 편의점까지 이동시킵니다.

 

Flood Fill의 방식이고, 길을 연결한다는 느낌으로 받아들이시면 되겠습니다.

	static void find_base(int i) {
		int[][] road = connect_road(i);
		Pos man = people[i];  // 이 사람의 베이스켐프를 지정할 것
		int distance = Integer.MAX_VALUE;

		for(int y = 0; y < n; y++) {
			for(int x = 0; x < n; x++) {
				if(map[y][x] == 1 && road[y][x] != 0 && distance > road[y][x]) {
					distance = road[y][x];
					man.y = y;
					man.x = x;
				}
			}
		}
		
		map[man.y][man.x] = -1;  // 이동 불가의 의미
	}

도로를 연결시켰으면 완전탐색을 통해 최단경로의 베이스캠프를 찾아냅니다.

 

베이스캠프를 찾을 때마다 대상자의 위치를 갱신하고 모든 탐색이 끝나면 해당 위치를 탐색 범위에서 제외하기 위해 -1로 값을 변경합니다.

 

참고로, 위와 같이 탐색을 하면, 가까운 베이스캠프가 여럿일 때, 행이 작고 열이 작은 순으로 베이스캠프를 선정할 수 있습니다.

	static void go_store(int i) {
		int[][] road = connect_road(i);
		Pos man = people[i];  // 이 사람의 베이스켐프를 지정할 것
		int distance = Integer.MAX_VALUE;
		int final_y = -1, final_x = -1;
		
		for(int[] d: directions) {
			int my = man.y + d[0], mx = man.x + d[1];
			if(0 <= my && my < n && 0 <= mx && mx < n && road[my][mx] != 0 && distance > road[my][mx]) {
				distance = road[my][mx];
				final_y = my;
				final_x = mx;
			}
		}
		
		man.y = final_y;
		man.x = final_x;
	}

편의점 이동입니다. 마지막으로 위치한 곳을 저장하기 위해 변수를 두고 각 방향을 전부 확인합니다.

 

이동은 범위가 유효하고, 도로가 연결되어 있으며 최단 거리인 곳으로 수행합니다.

	static void update_info() {
		for(int i = 1; i <= m; i++) {
			Pos man = people[i];
			Pos store = stores[i];
			if(man.y == store.y && man.x == store.x) {
				arrive[i] = true;
				map[store.y][store.x] = -1;
				
			}
		}
	}

편의점으로의 이동이 끝났다면, 모든 사람을 확인하며 편의점에 도착했는지 확인합니다.

 

도착했다면 범위에서 제외하기 위해 값을 변경해 줍니다.

	static boolean check_terminate() {
		for(int i = 1; i <= m; i++) {
			if(!arrive[i]) {
				return false;
			}
		}
		return true;
	}

마지막으로 종료 조건 확인입니다.

 

모든 사람을 확인하며 편의점 도착했는지 확인합니다. 한 명이라도 도착을 못 했다면 false를 반환해 이동을 지속시킵니다.

---

[전체 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m;
	static int[][] map;
	static int y, x;
	static boolean[] arrive;
	static Pos[] people;
	static Pos[] stores;
	static int time = 0;
	static int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
	
	static class Pos {
		int y, x;
		
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		arrive = new boolean[m + 1];
		people = new Pos[m + 1];
		stores = new Pos[m + 1];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken()) - 1;
			x = Integer.parseInt(st.nextToken()) - 1;
			stores[i] = new Pos(y, x);
			people[i] = new Pos(-1, -1);
		}
		
		solve();
	}
	
	static int[][] connect_road(int i) {
		Pos store = stores[i];  // 해당 편의점을 기점으로 가장 가까운 편의점 탐색
		int[][] visited = new int[n][n];
		visited[store.y][store.x] = 1;
		ArrayDeque<Pos> dq = new ArrayDeque<>();
		dq.add(store);
		
		while(!dq.isEmpty()) {
			Pos current = dq.poll();
			for(int[] d: directions) {
				int my = current.y + d[0], mx = current.x + d[1];
				if(0 <= my && my < n && 0 <= mx && mx < n && visited[my][mx] == 0 && map[my][mx] != -1) {
					visited[my][mx] = visited[current.y][current.x] + 1;
					dq.add(new Pos(my, mx));
				}
			}
		}
		
		return visited;
	}
	
	static void find_base(int i) {
		int[][] road = connect_road(i);
		Pos man = people[i];  // 이 사람의 베이스켐프를 지정할 것
		int distance = Integer.MAX_VALUE;

		for(int y = 0; y < n; y++) {
			for(int x = 0; x < n; x++) {
				if(map[y][x] == 1 && road[y][x] != 0 && distance > road[y][x]) {
					distance = road[y][x];
					man.y = y;
					man.x = x;
				}
			}
		}
		
		map[man.y][man.x] = -1;  // 이동 불가의 의미
	}
	
	static void go_store(int i) {
		int[][] road = connect_road(i);
		Pos man = people[i];  // 이 사람의 베이스켐프를 지정할 것
		int distance = Integer.MAX_VALUE;
		int final_y = -1, final_x = -1;
		
		for(int[] d: directions) {
			int my = man.y + d[0], mx = man.x + d[1];
			if(0 <= my && my < n && 0 <= mx && mx < n && road[my][mx] != 0 && distance > road[my][mx]) {
				distance = road[my][mx];
				final_y = my;
				final_x = mx;
			}
		}
		
		man.y = final_y;
		man.x = final_x;
	}
	
	static void update_info() {
		for(int i = 1; i <= m; i++) {
			Pos man = people[i];
			Pos store = stores[i];
			if(man.y == store.y && man.x == store.x) {
				arrive[i] = true;
				map[store.y][store.x] = -1;
				
			}
		}
	}
	
	static boolean check_terminate() {
		for(int i = 1; i <= m; i++) {
			if(!arrive[i]) {
				return false;
			}
		}
		return true;
	}
	
	static void solve() {
		while(!check_terminate()) {
			time += 1;
			for(int i = 1; i <= m; i++) {
				if(arrive[i] || people[i].y == -1 && people[i].x == -1) {  // 편의점에 도착했거나, 아직 베이스켐프가 아니라면
					continue;
				}
				go_store(i);
			}
			update_info();  // 모든 사람들의 이동이 끝났을 때, 편의점을 막을지 말지 확인해야 함
			if(time <= m) {  // 사람들을 베이스캠프로
				find_base(time);
			}
		}

		System.out.println(time);
	}
}

---