Node.js) 백준 19238번 : 스타트 택시

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

 

위쪽 왼쪽을 우선으로 탐색해주면 가장 가깝고,  행번호, 열번호가 작은 승객을 찾을 수 있다고 생각했는데, 그게 아니었음

 

거리가 최소인 승객을 전부 찾은 다음에 정직하게 행번호, 열번호를 비교해줘야함. 

 

 

 

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const fs = require('fs');
const input = fs
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M, F] = input.shift();

// 지도
let board = input.splice(0, N);

//택시 시작 위치
let [tx, ty] = input.shift().map((v) => v - 1);

// 승객 위치, 목적지 위치를 계산하기 좋게 1씩 빼주고,
let p = input.map((v) => v.map((x) => x - 1));

//승객 지도
//승객이 있는 위치를 지도에 표시
// 1번승객은 -1, 2번승객은 -2로 지도에 표시
// 승객 옮기면 그 칸은 0으로 바꿔줄꺼
let sMap = board.map((v) => [...v]);
p.forEach((v, i) => {
	const [sx, sy] = v;
	sMap[sx][sy] = -(i + 1);
});

// 남아잇는 승객의 수
let remain = p.length;

//택시의 연료
let fuel = F;

// 승객 위치에서 목적지 위치까지의 최단거리를 계산하는 함수
function calcMinDist(sx, sy, ex, ey) {
	const dx = [-1, 0, 1, 0];
	const dy = [0, -1, 0, 1];
	let dist = Infinity;
	let visited = Array.from(Array(N), () => Array(N).fill(false));
	visited[sx][sy] = true;
	const q = new Queue();
	q.push([sx, sy, 0]);
	while (q.length > 0) {
		const [x, y, c] = q.pop();
		if (x == ex && y == ey) {
			dist = c;
			return dist;
		}

		for (let i = 0; i < 4; i++) {
			const nx = x + dx[i];
			const ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] == 1 || visited[nx][ny]) continue;
			visited[nx][ny] = true;
			q.push([nx, ny, c + 1]);
		}
	}
	return dist;
}

//승객이 모두 이동할 때까지
while (remain > 0) {
	//택시 위치에서 각 승객이 있는 위치를 bfs로 탐색
	const q = new Queue();
	const dx = [-1, 0, 1, 0];
	const dy = [0, -1, 0, 1];

	// 최단거리가 동일한 승객들
	// 이후 행번호가 작은순, 열번호가 작은 순으로 정렬한 후 가장 첫번째 승객에게 찾아갈거임
	let passenger = null;

	//승객까지의 최단거리
	let minDist = Infinity;

	// 지나간 곳 표시
	let visited = Array.from(Array(N), () => Array(N).fill(false));
	visited[tx][ty] = true;

	q.push([tx, ty, 0]);
	while (q.length > 0) {
		const [x, y, c] = q.pop();
		// -1,-2 등 승객이 있는 곳이면
		if (sMap[x][y] < 0) {
			// 해당 승객의 번호
			const nowPassenger = -sMap[x][y] - 1;

			//해당 승객까지의 거리가 현재까지 찾은 최단 거리보다 작으면
			if (c < minDist) {
				//최단거리도 바꿔주고
				minDist = c;

				// 태우러갈 승객도 바꿔주고
				passenger = nowPassenger;

				// 해당 승객까지의 거리가 현재까지의 최단거리와 같으면
			} else if (c == minDist) {
				const prev = p[passenger];
				const now = p[nowPassenger];
				// 지금 선택된 승객의 행번호가 방금전 선택된 승객의 행번호보다 작으면 교체
				if (prev[0] > now[0]) {
					passenger = nowPassenger;
					// 두 승객의 행번호가 같고, 지금 선택된 승객의 열번호가 방금 전 선택된 승객의 열번호보다 작으면 교체
				} else if (prev[0] == now[0]) {
					if (prev[1] > now[1]) {
						passenger = nowPassenger;
					}
				}
			}
			continue;

			// 승객이 있는 위치가 아니면 상하좌우로 이동
		} else {
			for (let k = 0; k < 4; k++) {
				const nx = x + dx[k];
				const ny = y + dy[k];
				// 지도를 벗어나거나, 벽이거나, 이미 지나온 곳이면 무시
				if (nx < 0 || nx >= N || ny < 0 || ny >= N || sMap[nx][ny] == 1 || visited[nx][ny])
					continue;

				// 그게 아니라면 지나온곳 표시하고, 다음 경로를 큐에 추가
				visited[nx][ny] = true;
				q.push([nx, ny, c + 1]);
			}
		}
	}

	// 태울 수 있는 승객이 없는 경우 종료
	if (minDist == Infinity || passenger == null || fuel < minDist) {
		console.log(-1);
		return;
	}
	// 연료 소비해주고,
	fuel -= minDist;

	const [sx, sy, ex, ey] = p[passenger];

	// 승객 위치에서 목적지 위치까지 최단거리구해서
	const dist2 = calcMinDist(sx, sy, ex, ey);

	// 갈 수 없거나 , 연료가 없으면 종료
	if (dist2 == Infinity || fuel < dist2) {
		console.log(-1);
		return;
	}

	// 연료소비하고, 충전해주고,
	fuel += dist2;

	// 택시위치 갱신해주고
	tx = ex;
	ty = ey;

	//옮긴 승객은 승객지도에서 지워주고
	sMap[sx][sy] = 0;

	//남은 승객에서 1빼주고
	remain -= 1;
}
// 마지막에 남은 연료 출력
console.log(fuel);