풀이 방법
bfs를 이용해서 풀이했다.
이 문제에서 생각해야 할게 각 손님마다 출발지와 목적지는 다르고 출발지는 각각 다르다는 말이다.
결국 손님들의 목적지는 같을 수 있고 한 손님의 출발지가 다른 손님의 목적지가 되는 경우가 생긴다.
이 경우만 고려해서 잘 풀어주면 된다.
내 코드
package com.company;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int[][] way = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static int[][] arr;
static int N, M, fuel;
static boolean[][] visited;
static HashMap<Integer, int[]> map = new HashMap<>();
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());
fuel = Integer.parseInt(st.nextToken());
arr = 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++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
int curX = Integer.parseInt(st.nextToken());
int curY = Integer.parseInt(st.nextToken());
for (int i = 2; i < M + 2; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = i;
map.put(i, new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
}
for (int i = 0; i < M; i++) {
Node n = find(new Node(curX, curY, 0), 0, 0);
if (n == null || fuel - n.dis < 0) {
System.out.println(-1);
return;
}
curX = n.x;
curY = n.y;
fuel -= n.dis;
n.dis = 0;
int[] des = map.get(arr[n.x][n.y]);
n = find(n, des[0], des[1]);
arr[curX][curY] = 0;
if (n == null || fuel - n.dis < 0) {
System.out.println(-1);
return;
}
fuel += n.dis;
curX = n.x;
curY = n.y;
}
System.out.println(fuel);
}
static Node find(Node n, int x, int y) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(n);
visited = new boolean[N + 1][N + 1];
while (!pq.isEmpty()) {
Node node = pq.poll();
if(visited[node.x][node.y]){
continue;
}
if (x == 0 && y == 0 && arr[node.x][node.y] > 1) {
return node;
} else if (node.x == x && node.y == y) {
return node;
}
for (int i = 0; i < 5; i++) {
int tempX = node.x + way[i][0];
int tempY = node.y + way[i][1];
if (tempX <= N && tempX > 0 && tempY <= N && tempY > 0 && arr[tempX][tempY] != 1 && !visited[tempX][tempY]) {
pq.add(new Node(tempX, tempY, node.dis + 1));
}
}
visited[node.x][node.y] = true;
}
return null;
}
static class Node implements Comparable<Node> {
int x, y, dis;
public Node(int x, int y, int dis) {
this.x = x;
this.y = y;
this.dis = dis;
}
@Override
public int compareTo(Node o) {
if (dis - o.dis != 0)
return dis - o.dis;
else if (x - o.x != 0) {
return x - o.x;
}
return y - o.y;
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
최소 회의실 개수 - 19598번 (0) | 2022.02.07 |
---|---|
가장 긴 바이토닉 부분 수열 - 11054번 (0) | 2022.02.07 |
소수상수근 - 9421번 (0) | 2022.02.07 |
스카이라인 쉬운거 - 1863번 (0) | 2022.02.04 |
불 - 5427번 (0) | 2022.01.24 |