문제 탐색하기
입력 자료 정리
- N은 배열의 가로,세로크기를 의미한다
- M은 승객의 개수, 이어서 들어오는 값은 최초 연료의 양이다
- N X N의 입력값은 활동할 영역의 상태이다. 0이면 빈칸, 1이면 벽이다
벽은 지나갈 수 없고 빈칸은 지나갈 수 있다 - 이어서 들어오는 두가지 값은 택시의 최초 Y,X위치다
- 이제 M개의 입력값이 들어온다. 각각 승객의 최초 Y,X위치이고 목적지 Y,X위치다
해결방법 추론
- 입력값도 매우 작으므로
현재 택시의 위치에서 가장 가까운 승객의 위치를 bfs로 찾은다음,
다시 그 승객의 목적지를 bfs로 찾으면 될 것이다 - 이때 모든 승객을 태워야 하므로 시뮬레이션 형식으로 진행해야하며,
bfs의 탐색 우선순위가 존재하므로 우선순위 큐를 이용해서 bfs 탐색을 진행하면 되겠다고 생각했다! - 입력값이 매우 작고, 좌표평면 탐색이며 우선순위라는 문제의 힌트 덕분에 쉽게 해결방법을 추론할 수 있었다
- 상태관리 구현만 조금 신경쓴다면 어렵지 않게 문제를 해결할 수 있을 것이다
시간복잡도 계산
- 시간복잡도는 먼저 m만큼의 시뮬레이션을 진행하므로 m의 연산이 발생한다
- bfs는 우선순위 큐를 사용하므로 logn^2의 연산이 발생하며, 이것을 n^2의 배열에서 진행하므로
2x n^2logn의 연산이 발생한다 - 상수를 제거하고 정리하면 O(m x n^2logn)의 시간복잡도가 발생하며 시간제한안에 문제를 해결할 수 있다!
코드 설계하기
입력값 상태 관리
- 각 크기 입력값들은 int형 변수로 관리하며, 활동 영역의 지도와 방문배열은 2차원 배열로 선언한다
각각 int형과 boolean형이다 - 4방 탐색 편의 배열을 선언하며 택시의 시작위치와 출발위치를 변수로 각각 받는다
- 택시의 현재 위치와 이동거리를 보관할 Taxi 클래스를 하나 선언했다
- 또한 승객의 정보를 담기 위해 승객의 시작좌표와 목적지 좌표를 각각 필드로 가진다
- 정답 출력을 위한 ans변수는 -1로 초기화했으며, 만약 더이상 전진하지 못하는 경우를 구분하기 위해 boolean 타입의 isOk를 true로 선언했따
시뮬레이션 설계
- m의 개수만큼 시뮬레이션을 진행한다
- 먼저 가장 가까운 승객을 찾는 BFS를 통해 승객의 번호를 구한다
- 만약 승객이 0번이거나 더이상 전진할 수 없는 경우 ans를 -1로 바꾸고 시뮬레이션을 종료한다
- 이어서 해당 승객의 정보로 택시를 목적지까지 이동시키는 bfs를 실행한다
- 이제 택시의 현재 위치를 승객의 목적지로 바꾼다
- 마지막에도 더이상 전진할 수 있는지 여부를 확인하고 가능하다면 ans를 현재 남은 연료로 바꾼다
BFS 설계
(공통) 설계
- 방문배열을 초기화하고 우선순위큐를 사용한다
우선순위큐의 정렬은 거리 -> Y좌표 -> X좌표를 기준으로 하며 모두 오름차순한다 - 시작위치를 우선순위 큐에 넣고 이동거리를 0으로 한다. 이어서 해당 지점을 방문체크한다
- 4방 탐색을 하는 BFS를 실행한다. 범위를 벗어나지 않거나 벽이 아니거나 방문하지 않았다면
방문하고 우선순위 큐에 이동거리를 1 증가해서 넣는다
승객을 찾는 경우
- 종료조건만 조금 다르다.
- 만약 현재 위치가 0이 아닐 경우 승객의 위치에 도달했다는 것이므로
연료를 거리만큼 줄이고 해당 승객의 번호를 리턴하도록한다 - 대신 그전에 연료가 0보다 작은지 확인하고 맞다면 더이상 전진할 수 없다는 isOk를 false로 한다
- 그리고 승객의 지점은 0으로 처리한다
승객의 목적지까지 이동하는 경우
- 이번에는 승객의 목적지에 도달한 경우다.
- 연료를 똑같이 거리만큼 줄이고 연료가 0보다 작은 경우도 체크한다
- 마지막에는 조금 다른데 연료를 현재 거리의 2배로 더해준다
출력값 설계
- 완성한 ans를 출력하면 정답이 된다.
정답 코드
import java.io.*;
import java.util.*;
class Client{
int startY;
int startX;
int endY;
int endX;
public Client(int startY, int startX, int endY, int endX) {
this.startY = startY;
this.startX = startX;
this.endY = endY;
this.endX = endX;
}
}
class Taxi{
int nowY;
int nowX;
int dist;
public Taxi(int nowY, int nowX, int dist) {
this.nowY = nowY;
this.nowX = nowX;
this.dist = dist;
}
}
public class Main {
static int n;
static int m;
static int fuel;
static int[][] arr;
static int ans = -1;
static Client[] clients;
static boolean[][] visited;
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static int startY;
static int startX;
static boolean isOk = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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+1; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < n+1; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] == 1){
arr[i][j] = -1;
}
}
}
clients = new Client[m+1];
st = new StringTokenizer(br.readLine());
startY = Integer.parseInt(st.nextToken());
startX = Integer.parseInt(st.nextToken());
for (int i = 1; i < m+1; 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());
arr[a][b] = i;
clients[i] = new Client(a,b,c,d);
}
while(m --> 0) {
int client = findClient();
if(client == 0 || !isOk){
ans = -1;
break;
}
bfs(clients[client].startY, clients[client].startX, clients[client].endY, clients[client].endX);
startY = clients[client].endY;
startX = clients[client].endX;
if(!isOk){
ans = -1;
break;
}
ans = fuel;
}
bw.write(ans+"");
br.close();
bw.close();
}
private static int findClient() {
visited = new boolean[n+1][n+1];
PriorityQueue<Taxi> pq = new PriorityQueue<>((o1, o2) -> {
if(o1.dist == o2.dist){
if (o1.nowY == o2.nowY){
return o1.nowX - o2.nowX;
}
return o1.nowY - o2.nowY;
}
return o1.dist - o2.dist;
});
pq.add(new Taxi(startY, startX, 0));
visited[startY][startX] = true;
while(!pq.isEmpty()){
Taxi now = pq.poll();
if(arr[now.nowY][now.nowX] != 0){
fuel -= now.dist;
if(fuel < 0){
isOk = false;
}
int meet = arr[now.nowY][now.nowX];
arr[now.nowY][now.nowX] = 0;
return meet;
}
for (int i = 0; i < 4; i++) {
int ny = now.nowY + dy[i];
int nx = now.nowX + dx[i];
if(isRange(ny, nx) && arr[ny][nx] != -1 && !visited[ny][nx]){
visited[ny][nx] = true;
pq.add(new Taxi(ny,nx, now.dist + 1));
}
}
}
return 0;
}
private static void bfs(int startY, int startX, int endY, int endX) {
visited = new boolean[n+1][n+1];
PriorityQueue<Taxi> pq = new PriorityQueue<>((o1, o2) -> {
if(o1.dist == o2.dist){
if (o1.nowY == o2.nowY){
return o1.nowX - o2.nowX;
}
return o1.nowY - o2.nowY;
}
return o1.dist - o2.dist;
});
pq.add(new Taxi(startY,startX,0));
visited[startY][startX] = true;
while(!pq.isEmpty()){
Taxi now = pq.poll();
if(now.nowY == endY && now.nowX == endX){
fuel -= now.dist;
if(fuel < 0){
isOk = false;
}
fuel += now.dist*2;
return;
}
for (int i = 0; i < 4; i++) {
int ny = now.nowY + dy[i];
int nx = now.nowX + dx[i];
if(isRange(ny, nx) && arr[ny][nx] != -1 && !visited[ny][nx]){
visited[ny][nx] = true;
pq.add(new Taxi(ny,nx, now.dist + 1));
}
}
}
isOk = false;
}
private static boolean isRange(int y, int x){
return y > 0 && y <= n && x > 0 && x <= n;
}
}문제 링크
Software Developer