📎 삼성 SW 역량테스트 2022 하반기 오후 1번 문제
✨ 언어: Java, 수행시간: 100ms, 메모리: 9MB, 소요 시간: 120분
🗝️ 키워드: 구현, 시뮬레이션, BFS
➊ 문제 정의
n * n 격자 위에 베이스 캠프와 편의점의 위치가 주어진다.
이때, m명의 사람과 m개의 편의점이 존재하며
베이스캠프의 개수는 m개보다 크거나 같다.
모든 사람은 시뮬레이션 시작 시 격자 밖에 위치한다.
만약 m = 3이라고 가정해보겠다.
시뮬레이션이 시작되면,
1번 사람은 1초에 격자 위 베이스캠프로 이동한다.
2번 사람은 2초에 격자 위 베이스캠프로 이동한다.
3번 사람은 3초에 격자 위 베이스캠프로 이동한다.
즉, m번 사람은 m초가 되어서야 비로소 격자 위 베이스캠프로 이동한다.
모든 사람은 1초당 1칸씩 전진할 수 있으며
그들의 목표는 각자 m번 편의점으로 이동하는 것이다.
모든 사람이 자신이 목표한 편의점까지 이동을 마치고 나면
시뮬레이션이 종료되며 몇 초가 걸리는지 반환해야 한다.
이때 베이스캠프는 m개 이상인데,
각 사람이 어떤 베이스캠프를 선택할지에 대한 기준은 다음과 같다.
1번 사람은 1번 편의점으로 이동해야 하며
1번 편의점까지의 거리가 가장 가까운 베이스캠프를 택한다.
2번 사람은 2번 편의점으로 이동해야 하며
2번 편의점까지의 거리가 가장 가까운 베이스캠프를 택한다.
3번 사람은 3번 편의점으로 이동해야 하며
3번 편의점까지의 거리가 가장 가까운 베이스캠프를 택한다.
🤔 그렇다면 단순히 맨해튼 거리로 거리를 구할 수 있지 않을까?
하지만 문제의 조건에 따르면
🚨 베이스캠프 혹은 편의점은 지나갈 수 없도록 비활성화될 수 있다.
따라서 단순 맨해튼 거리를 이용하면 문제를 해결할 수 없고
BFS을 통해 너비 우선 탐색을 진행하여 거리를 측정해야 한다.
빵을 구하고 싶은 사람들은 다음과 같은 방법으로 움직인다.
이 3가지 행동은 총 1분 동안 진행되며,
정확히 1 → 2 → 3 순서로 진행되어야 한다!
// ①
격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다.
최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면
↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다.
여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여
도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.// ②
만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고,
이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다.
격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.// ③
현재 시간이 t분이고 t ≤ m를 만족한다면,
t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다.
여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다.
가장 가까운 베이스캠프가 여러 가지인 경우에는,
그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다.
t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
이때부터 다른 사람들은 해당 베이스 캠프가 있는 칸을 지나갈 수 없게 됩니다.
t번 사람이 편의점을 향해 움직이기 시작했더라도
해당 베이스 캠프는 앞으로 절대 지나갈 수 없음에 유의합니다.
마찬가지로 해당 턴 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.➋ 문제 설계 및 코드 작성
① 클래스 정의 (객체 지향적 사고)
위의 문제에서 총 3 종류의 객체가 등장한다.
- 베이스캠프 (BaseCamp)
- 편의점 (Store)
- 사람 (Person)
따라서 위의 객체를 클래스로 정의해주었다.
또한 boolean 2차원 배열인 map을 Main 클래스에서 static 으로 정의하여
해당 칸을 지나갈 수 있는지 여부를 관리하였다.
② 최단 거리 계산 (BFS)
시뮬레이션을 진행하다 아래의 최단 거리를 계산해야 한다.
- 베이스캠프와 편의점 사이의 거리
- 현재 사람의 위치와 편의점 사이의 거리
그러나 중간에 지나갈 수 없는 칸이 존재하기 때문에
BFS을 활용하여 최단 거리를 계산하였다.
🚨 모든 사람이 1칸씩 이동할 때마다 동적으로 특정 칸이 지나갈 수 없도록 막히기 때문에 1초마다 BFS을 진행해주어야 한다!
모든 사람은 상(↑), 좌(←), 우(→), 하(↓) 중 하나로 이동해야 한다.
따라서 어떤 방향으로 이동해야 할지 결정하기 위해
다음과 같이 총 4번의 BFS을 진행하였다.
- 위로 1칸 이동한 상태에서 BFS 진행
- 좌로 1칸 이동한 상태에서 BFS 진행
- 우로 1칸 이동한 상태에서 BFS 진행
- 하로 1칸 이동한 상태에서 BFS 진행
이렇게 4번의 BFS을 진행하고
가장 짧은 최단 거리를 반환하는 방향으로 최종 이동하였다.
(위의 방법이 비효율적일 수 있지만,
BFS 함수는 편의점과 베이스캠프 사이의 거리를 구하는 데에도 사용되기 때문에
범용적인 BFS 함수의 코드를 작성하다보니 그리 되었다...)
③ 해당 칸 비활성화
칸이 지나갈 수 없도록 비활성화되는 조건은 다음 2가지이다.
- 사람이 베이스캠프로 이동하고 난 다음
- 사람이 편의점으로 이동하고 난 다음
해당 칸을 지나갈 수 없음, 즉 비활성화인 상태를 표시하기 위해 2가지를 실행하였다.
- boolean 타입의 2차원 배열인 map에
true값으로 표시 - BaseCamp 객체와 Store 객체의 필드인
disable을true값으로 표시
④ 시뮬레이션 진행
각 사람들이 1초마다 실행할 행동을 그대로 1 → 2 → 3 순서대로 실행한다.
반복문이 1번 돌 때마다 다음의 순서로 진행한다.
time+1 증가- ① 격자 안의 사람들 편의점으로 1칸 이동
- ② 편의점에 도착했는지 확인
- ③ 격자 밖의 사람 베이스캠프로 이동
- 모든 사람이 편의점에 도착했는지 여부를 확인
→ 모두 도착했다면 루프 종료 조건 만족
이때 goToStore(), checkArrived(), setDestStore(), goToBaseCamp() 등의 메소드는 각 객체의 속성과 밀접한 관련이 있기 때문에 클래스 안에 정의해주었다.
➌ 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class 코드트리빵 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer tokens;
private static int N;
private static int M;
private static boolean[][] map; // 지나갈 수 있는지 여부 기록
private static Store[] stores;
private static Person[] people;
private static ArrayList<BaseCamp> baseCamps;
private static int[][] moves = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
private static int simulation() {
int time = 0;
while (true) {
time++;
// ① 격자 안의 사람들 편의점으로 1칸 이동
for (Person person : people) {
person.goToStore();
}
// ② 편의점에 도착했는지 확인
for (Person person : people) {
person.checkArrived();
}
// ③ 격자 밖의 사람 베이스캠프로 이동
if (time <= M) {
people[time - 1].setDestStore();
people[time - 1].goToBaseCamp();
}
// ④ 모든 사람이 편의점에 도착했으면 종료
boolean flag = true;
for (Person person : people) {
if (!person.isArrived) {
flag = false;
break;
}
}
if (flag) {
break;
}
}
return time;
}
private static void init() throws IOException {
tokens = new StringTokenizer(br.readLine());
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
map = new boolean[N][N];
baseCamps = new ArrayList<>();
int num = 1;
for (int i = 0; i < N; i++) {
tokens = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int grid = Integer.parseInt(tokens.nextToken());
if (grid == 1) {
baseCamps.add(new BaseCamp(num++, i, j));
}
}
}
stores = new Store[M];
people = new Person[M];
for (int i = 0; i < M; i++) {
tokens = new StringTokenizer(br.readLine());
int r = Integer.parseInt(tokens.nextToken()) - 1;
int c = Integer.parseInt(tokens.nextToken()) - 1;
stores[i] = new Store(i + 1, r, c);
people[i] = new Person(i + 1, -1, -1);
}
}
public static void main(String[] args) throws IOException {
init();
int answer = simulation();
System.out.println(answer);
}
// 시작 좌표로부터 목표 좌표까지의 최단 거리 반환
private static int bfs(int sr, int sc, int dr, int dc) {
ArrayDeque<int[]> dq = new ArrayDeque<>();
boolean[][] visited = new boolean[N][N];
dq.offer(new int[] {sr, sc, 0});
while (!dq.isEmpty()) {
int[] cur = dq.poll();
int r = cur[0];
int c = cur[1];
int distance = cur[2];
if (r == dr && c == dc) {
return distance;
}
if (r < 0 || c < 0 || r >= N || c >= N) {
continue;
}
if (map[r][c]) {
continue;
}
if (visited[r][c]) {
continue;
}
visited[r][c] = true;
for (int[] move : moves) {
int nr = r + move[0];
int nc = c + move[1];
dq.addLast(new int[] {nr, nc, distance + 1});
}
}
return Integer.MAX_VALUE;
}
static class Store {
int num;
int r;
int c;
boolean disable;
Store(int num, int r, int c) {
this.num = num;
this.r = r;
this.c = c;
this.disable = false;
}
void disable() {
this.disable = true;
map[r][c] = true; // 맵에서 비활성화
}
// 편의점과 가장 가까운 베이스캠프의 번호를 반환
BaseCamp getMinBaseCamp() {
int minDistance = Integer.MAX_VALUE;
BaseCamp minBaseCamp = null;
for (BaseCamp baseCamp: baseCamps) {
int distance = baseCamp.getDistance(this);
if (minDistance > distance) {
minDistance = distance;
minBaseCamp = baseCamp;
}
}
return minBaseCamp;
}
}
static class Person {
int num;
int r;
int c;
boolean isDeparted;
boolean isArrived;
Store destStore;
Person(int num, int r, int c) {
this.num = num;
this.r = r;
this.c = c;
this.isDeparted = false;
this.isArrived = false;
}
void setDestStore() {
this.destStore = stores[num - 1];
}
boolean canMove() {
return isDeparted && !isArrived;
}
void checkArrived() {
if (!canMove()) return;
if (this.r == this.destStore.r && this.c == this.destStore.c) {
this.isArrived = true;
this.destStore.disable();
}
}
// 편의점 방향을 향해서 최단 거리로 1칸 이동
void goToStore() {
if (!canMove()) return;
int minDistance = Integer.MAX_VALUE;
int[] minMove = {0, 0};
for (int[] move: moves) {
int sr = r + move[0];
int sc = c + move[1];
int distance = bfs(sr, sc, destStore.r, destStore.c);
if (minDistance > distance) {
minDistance = distance;
minMove = move;
}
}
this.r += minMove[0];
this.c += minMove[1];
}
void goToBaseCamp() {
BaseCamp destBaseCamp = this.destStore.getMinBaseCamp();
destBaseCamp.disable();
this.r = destBaseCamp.r;
this.c = destBaseCamp.c;
this.isDeparted = true;
}
}
static class BaseCamp {
int num;
int r;
int c;
boolean disable;
BaseCamp(int num, int r, int c) {
this.num = num;
this.r = r;
this.c = c;
this.disable = false;
}
void disable() {
this.disable = true;
map[r][c] = true; // 맵에서 비활성화
}
// 베이스캠프에서부터 편의점까지의 거리 반환
int getDistance(Store store) {
if (disable) return Integer.MAX_VALUE;
return bfs(r, c, store.r, store.c);
}
}
}
