https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
코드설명
시뮬레이션 + 구현 + BFS(너비우선탐색) + 우선순위큐(Priority Queue) + 해쉬맵(HashMap) 을 활용하여 해결할 수 있습니다.
처음에 풀었을때는 우선순위큐 2개를 사용하여 가장 가까운 거리를 가져오도록 하여 코드의 복잡도가 높았습니다.
무엇보다도 BFS를 모든 점에 해당하여 실행했기 때문에 시간초과가 날 수 밖에 없었습니다.
따라서, 정답은 맞았지만 시간초과가 나고, 코드를 깔끔하게 다시 고쳐보았습니다.
주요 변수 및 자료구조입니다.
- N, M, K: 맵의 크기, 사람의 수, 초기 연료 양을 나타내는 변수
- map: 지도 정보를 저장하는 2차원 배열
- dx, dy: 상하좌우 이동을 나타내는 배열
- visited: 방문 여부를 저장하는 2차원 배열
- car: 택시의 현재 위치와 연료 상태를 저장하는 객체
- MAXDISTANCE: 최대 거리를 나타내는 상수
- pHashMap: 각 사람의 정보를 저장하는 해시맵
- targetPerson: 현재 이동 중인 사람의 정보를 저장하는 객체
- answer: 결과를 저장하는 변수
main 함수
- 입력을 받고, 초기 맵 상태를 설정한다.
- 각 택시에서 모든 사람의 시작점까지의 최단 거리를 계산하여 우선순위 큐에 저장한다.
- 택시가 모든 사람을 데려다줄 때까지 반복한다.
- 각 단계에서 택시가 가장 가까운 사람을 찾아 데리러 가고, 이동한 후에는 해당 사람의 도착 지점까지 이동한다.
- 이동 중 연료가 다 떨어지면 -1을 출력하고, 모든 사람을 데려다준 경우 남은 연료를 출력한다.
- carToPeopleBFS 함수
- 택시에서 가장 가까운 사람을 찾는 BFS 함수
- 우선순위 큐를 사용하여 거리가 가까운 순서대로 탐색한다. 이때 PriorityQueue를 활용하여 별도의 처리 없이 가장 가까운 사람과 그런 승객이 여러명일경우 행번호가 가장 작은 승객과 열 번호가 가장 작은승객을 별도의 처리 없이 빠르게 찾을 수 있습니다. BFS에서 PriorityQueue를 활용하는 경우입니다.
- carStartToEndBFS 함수
- 택시가 사람을 데리러 간 후 목적지로 이동하는 BFS 함수
- Person 및 Car 클래스
- Person 클래스: 사람의 시작점과 도착점을 저장하는 클래스
- Car 클래스: 택시의 위치와 연료 상태를 저장하는 클래스
이 문제에서 느낀점은, 문제 구현에 있어서 어려운 문제는 아니었습니다.
다만, 어떻게 코드를 짜야 내가 실수없이 짤수 있을까에 대한 고민이 필요한 문제라고 생각이 듭니다.
처음에 풀었을때는 우선순위큐 2개를 활용하여 각 사람들의 위치를 저장하다보니 택시에서 가장 가까운 사람을 찾을때도 매번 PQ를 순회하며 확인했어야했을 것 입니다. 하지만, MAP[i][j] = i 로 임의로 Index를 넣어서 회원들을 저장시킬경우 그러한 불필요한 연산을 줄여서 훨씬 빨라집니다.
또한, 내가 이번에 옮길 인원을 Global하게 targetPerson으로 두어서 손쉽게 접근할 수 있다는 것입니다.
Car 같은경우 처음부터 한개로 생각하여 Global하게 다루었지만, targetPerson 을 생각하지 못했었습니다.
또한 HashMap을 활용하여 Person 객체를 손쉽게 가져올 수 있었습니다. 물론, Person 배열 객체를 생성하여서도 진행할 수 있었겠지만, HashMap이 좀 더 직관적이라 느껴집니다.
이번 문제를 통해 HashMap, 문제를 최대한 간단하게 푸는방법에 대한 생각, 사용할 객체를 GLobal하게 사용하여 손쉽게 사용하는 점, 문제의 구조화에 대한 생각을 해보았습니다.
코드
시간초과를 해결하고 깔끔해진 코드.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int answer = 0;
public static int[][] map;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static boolean[][] visited;
public static Car car;
public static int MAXDISTANCE = 401;
public static HashMap<Integer, Person> pHashMap = new HashMap<>();
public static Person targetPerson = new Person(0,0,0,0);
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());
K = Integer.parseInt(st.nextToken());
map = new int[N+1][N+1];
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=1;j<=N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
int startCarR = Integer.parseInt(st.nextToken());
int startCarC = Integer.parseInt(st.nextToken());
car = new Car(startCarR, startCarC, K);
//1. 먼저 각 차의 시작점에서 각 사람의 시작점까지의 최단거리를 BFS로 모두 구해서 우선순위큐에 넣습니다.
for(int i=10;i<10 + M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
map[a][b] = i;
pHashMap.put(i, new Person(a, b, c, d));
}
while(M-- > 0) { //모든 사람을 다 데려다줄때까지.
int distance = carToPeopleBFS(); //택시에서 가장 가까운 사람을 찾아서 반환합니다.
if(distance >= MAXDISTANCE) {
answer = -1;
break;
}
car.energy -= distance;
car.r = targetPerson.sR; car.c = targetPerson.sC;
//택시가 시작점에서 도착점으로 이동합니다.
distance = carStartToEndBFS();
if(distance >= MAXDISTANCE) {
answer = -1;
break;
}
car.energy += distance;
car.r = targetPerson.eR; car.c = targetPerson.eC;
}
if(answer == -1) {
System.out.println(answer);
}else {
System.out.println(car.energy);
}
}
public static int carStartToEndBFS() {
Queue<Car> q = new LinkedList<>();
q.offer(car);
visited = new boolean[N+1][N+1];
visited[car.r][car.c]= true;
while(!q.isEmpty()) {
Car temp = q.poll();
if(temp.energy < temp.moved) { //만약 연료가 다 떨어진다면 이동을 멈춥니다.
continue;
}
if(targetPerson.eR == temp.r && targetPerson.eC == temp.c && temp.energy >= temp.moved) { //만약 사람이 존재한다면, pq에 넣습니다. PQ를 활용하기 때문에 가장 빨리 만나는점이 반드시 가장 가깝고, 열과 행이 작습니다.
return temp.moved;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 1 || nr > N || nc < 1 || nc > N) continue;
if(map[nr][nc] == 1) continue;
if(visited[nr][nc] == true) continue;
visited[nr][nc] = true;
q.offer(new Car(nr, nc, temp.energy, temp.moved + 1));
}
}
return MAXDISTANCE;
}
public static int carToPeopleBFS() {
PriorityQueue<Car> q = new PriorityQueue<>();
q.offer(car);
visited = new boolean[N+1][N+1];
visited[car.r][car.c]= true;
while(!q.isEmpty()) {
Car temp = q.poll();
if(temp.energy < temp.moved) { //만약 연료가 다 떨어진다면 이동을 멈춥니다.
continue;
}
if(map[temp.r][temp.c] >= 10) { //만약 사람이 존재한다면, pq에 넣습니다. PQ를 활용하기 때문에 가장 빨리 만나는점이 반드시 가장 가깝고, 열과 행이 작습니다.
targetPerson = pHashMap.get(map[temp.r][temp.c]);
map[targetPerson.sR][targetPerson.sC]= 0;
return temp.moved;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 1 || nr > N || nc < 1 || nc > N) continue;
if(map[nr][nc] == 1) continue;
if(visited[nr][nc] == true) continue;
visited[nr][nc] = true;
q.offer(new Car(nr, nc, temp.energy, temp.moved + 1));
}
}
return MAXDISTANCE;
}
}
class Person {
int sR;
int sC;
int eR;
int eC;
public Person(int sR, int sC, int eR, int eC) {
this.sR = sR;
this.sC = sC;
this.eR = eR;
this.eC = eC;
}
}
class Car implements Comparable<Car>{
int r;
int c;
int energy;
int moved;
public Car(int r, int c, int energy) {
this.r = r;
this.c = c;
this.energy = energy;
}
public Car(int r, int c, int energy, int moved) {
this.r = r;
this.c = c;
this.energy = energy;
this.moved = moved;
}
@Override
public int compareTo(Car other) {
if(this.moved > other.moved) { //거리가 가까운것이 우선순위가 큽니다.
return 1;
}else if(this.moved == other.moved) {
if(this.r > other.r) {
return 1;
}else if(this.r == other.r) {
if(this.c > other.c) {
return 1;
}else if(this.c == other.c) {
return 0;
}else {
return -1;
}
}else {
return -1;
}
}else {
return -1;
}
}
}
처음에 비효율적으로 해결한 코드입니다.
정답은 맞지만, 시간초과가 나고, 코드의 복잡성이 높습니다.
예를들어, 우선순위큐를 2개를 같이 사용하여 관리가 어렵습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int answer = 0;
public static int[][] map;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static boolean[][] visited;
public static int h = 0, w = 0;
public static Car car;
public static int MAXDISTANCE = 401;
public static PriorityQueue<Person> pq = new PriorityQueue<>();
public static PriorityQueue<Person> pqTemp = new PriorityQueue<Person>();
public static ArrayList<Person> pList = new ArrayList<>();
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());
K = Integer.parseInt(st.nextToken());
map = new int[N+1][N+1];
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=1;j<=N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
int startCarR = Integer.parseInt(st.nextToken());
int startCarC = Integer.parseInt(st.nextToken());
car = new Car(startCarR, startCarC, K);
//1. 먼저 각 차의 시작점에서 각 사람의 시작점까지의 최단거리를 BFS로 모두 구해서 우선순위큐에 넣습니다.
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
pqTemp.offer(new Person(a, b, c, d, MAXDISTANCE));
}
while(M-- > 0) { //모든 사람이 사라질때까지 작업할 것 입니다.
pq = pqTemp; //이전 값을 넣어줍니다.
pqTemp = new PriorityQueue<Person>(); //이떄 해당 변수는 지역변수이므로 해당코드처럼 초기화진행시켜야한다. 그렇지않으면 while문 돌때마다 pqTemp가 초기화되서 다음값에 pq값에 연결이 안됩니다. 즉, public static PriorityQueue<Person> pqTemp = new PriorityQueue<Person>(); 처럼 쓰면안됩니다.
//아직 남아있는 사람들 간에 작업을 진행합니다.
while(!pq.isEmpty()) {
Person p = pq.poll();
int calculateDistance = DistanceBetweenCarPersonBFS(new Person(p.sR, p.sC, p.eR, p.eC, 0), car);
//BFS 각 길이를 반환하면, 해당 값을 PriorityQueue에 넣어서 우선순위로 정렬시킵니다.
pqTemp.offer(new Person(p.sR, p.sC, p.eR, p.eC, calculateDistance));
}
//가장 가까운 사람의 값을 넣어줄것인데, 그 값에 해당하여 차를 움직임처리해주어야하므로 초기화시켜야합니다.
car.moved = 0;
car.energy -= pqTemp.peek().distance; // 연료 사용처리합니다.
if(car.energy < 0) {
answer = -1;
break;
}
car.r = pqTemp.peek().sR; car.c = pqTemp.peek().sC; //택시가 사람을 태우러 시작점에 도착했습니다.
if( BetweenStarttoEndBfs(pqTemp.poll(), car) == false) {
answer = -1;
break;
}
}
if(answer == -1) {
System.out.println(answer);
}else {
answer = car.energy;
System.out.println(answer);
}
}
//차에서 해당 위치로 이동시키기 위해 차의 연료를 이제 그 거리를 기준으로 실제로 이동시키는 함수입니다.
public static boolean BetweenStarttoEndBfs(Person p, Car c) {
int distanceAnswer = MAXDISTANCE; //만약 도착못하면 - 1 return 할것입니다.
Queue<Car> cq = new LinkedList<Car>();
visited = new boolean[N+1][N+1];
cq.offer(c);
visited[c.r][c.c] = true;
while(!cq.isEmpty()) {
Car cTemp = cq.poll();
if(cTemp.energy < cTemp.moved) { //만약 차의 연료로 갈 수 없다면, 중간에 멈추므로 -1 을 반환합니다.
continue;
}
if(cTemp.r == p.eR && cTemp.c == p.eC && c.energy >= cTemp.moved) {
distanceAnswer = cTemp.moved;
car.r = p.eR; car.c = p.eC; car.energy += cTemp.moved; car.moved = 0;
return true;
}
for(int dir = 0; dir<4; dir++) {
int nr = cTemp.r + dx[dir];
int nc = cTemp.c + dy[dir];
if(nr < 1 || nr > N || nc < 1 || nc > N) continue;
if(map[nr][nc] == 1) continue;
if(visited[nr][nc] == true) continue;
visited[nr][nc] = true;
cq.offer(new Car(nr, nc, cTemp.energy, cTemp.moved + 1));
}
}
return false;
}
//사람의 정보를 기준으로 차가 각 길이를 반환하는 함수입니다.
public static int DistanceBetweenCarPersonBFS(Person p, Car c) {
int distanceAnswer = MAXDISTANCE; //만약 도착못하면 - 1 return 할것입니다.
visited = new boolean[N+1][N+1];
Queue<Car> cq = new LinkedList<Car>();
visited[c.r][c.c] = true;
cq.offer(c);
while(!cq.isEmpty()) {
Car cTemp = cq.poll();
if(cTemp.energy < cTemp.moved) { //만약 차의 연료로 갈 수 없다면, 중간에 멈추므로 -1 을 반환합니다.
continue;
}
if(cTemp.r == p.sR && cTemp.c == p.sC && cTemp.energy >= cTemp.moved ) {
distanceAnswer = cTemp.moved;
return distanceAnswer;
}
for(int dir = 0; dir<4; dir++) {
int nr = cTemp.r + dx[dir];
int nc = cTemp.c + dy[dir];
if(nr < 1 || nr > N || nc < 1 || nc > N) continue;
if(map[nr][nc] == 1) continue;
if(visited[nr][nc] == true) continue;
visited[nr][nc] = true;
cq.offer(new Car(nr, nc, cTemp.energy, cTemp.moved + 1));
}
}
return distanceAnswer;
}
}
class Person implements Comparable<Person>{
int sR;
int sC;
int eR;
int eC;
int distance;
public Person(int sR, int sC, int eR, int eC, int distance) {
this.sR = sR;
this.sC = sC;
this.eR = eR;
this.eC = eC;
this.distance = distance;
}
@Override
public int compareTo(Person other) {
if(this.distance > other.distance) { //거리가 가까운것이 우선순위가 큽니다.
return 1;
}else if(this.distance == other.distance) {
if(this.sR > other.sR) {
return 1;
}else if(this.sR == other.sR) {
if(this.sC > other.sC) {
return 1;
}else if(this.sC == other.sC) {
return 0;
}else {
return -1;
}
}else {
return -1;
}
}else {
return -1;
}
}
}
class Car{
int r;
int c;
int energy;
int moved;
public Car(int r, int c, int energy) {
this.r = r;
this.c = c;
this.energy = energy;
}
public Car(int r, int c, int energy, int moved) {
this.r = r;
this.c = c;
this.energy = energy;
this.moved = moved;
}
}