[백준] 19238번 - 스타트 택시 (C++) 문제 및 풀이

문제) 백준 - BFS - 스타트 택시

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

19238번: 스타트 택시

 

BFS를 통해 택시에서 승객, 승객에서 목적지까지의 최단 거리를 연료를 고려하여 승객을 태웁니다. 

board: 택시가 활동할 영역의 지도이며 -1일 경우 벽, 0일 경우 빈칸, 1 이상일 경우 손님의 인덱스를 나타냅니다.

tempBoard: BFS를 진행할때 거리와 방문 여부를 함께 저장합니다.

coords: 승객의 좌표와 거리를 계산한 벡터 배열입니다. cmp 정렬을 통해 승객의 우선순위를 정합니다.

finished: 승객의 탑승여부를 나타냅니다.

BFS: 모든 승객의 거리와 좌표를 계산하여 coords에 push_back 합니다.

moveToDest: 최단거리인 승객이 정해졌을 때, 승객의 목적지까지의 거리를 반환합니다.

 

C++ 소스코드)

	void bfs(){
	coords.clear();
	memset(tempBoard, -1, sizeof(tempBoard));
	queue<p> q;
	tempBoard[TAXI.first][TAXI.second] = 0;
	q.push(TAXI);
	while(!q.empty()){
	int x = q.front().first;
	int y = q.front().second;
	q.pop();
	if(board[x][y] != -1 && board[x][y] != 0 && !finished[board[x][y]])
	coords.push_back({x, y, tempBoard[x][y]});
	for(int i = 0; i < 4; ++i){
	int nx = x + Dir[i].first;
	int ny = y + Dir[i].second;
	if(valid(nx, ny) && tempBoard[nx][ny] == -1 && board[nx][ny] != -1){
	tempBoard[nx][ny] = tempBoard[x][y] + 1;
	q.push({nx, ny});
	}
	}
	}
	}
	int moveToDest(p dest){
	memset(tempBoard, -1, sizeof(tempBoard));
	queue<p> q;
	tempBoard[TAXI.first][TAXI.second] = 0;
	q.push(TAXI);
	while(!q.empty()){
	int x = q.front().first;
	int y = q.front().second;
	q.pop();
	if(x == dest.first && y == dest.second)
	return tempBoard[x][y];
	for(int i = 0; i < 4; ++i){
	int nx = x + Dir[i].first;
	int ny = y + Dir[i].second;
	if(valid(nx, ny) && tempBoard[nx][ny]== -1 && board[nx][ny] != -1){
	q.push({nx ,ny});
	tempBoard[nx][ny] = tempBoard[x][y] + 1;
	}
	}
	}
	return -1;
	}

view raw 19238.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/19238_%EC%8A%A4%ED%83%80%ED%8A%B8%ED%83%9D%EC%8B%9C.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions