JUNGOL/Intermediate_Coder/그래프탐색-BFS/2578 : 버스 갈아타기

코딩 테스트/JUNGOL 2023. 5. 29. 15:54

Intermediate_Coder/그래프탐색-BFS/버스 갈아타기

문제

2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있다.

아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예이다.

수직선과 수평선이 만나는 교차점들 중 가장 왼쪽 아래 점의 위치는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (m,n)이다.

이 도로망을 운행하는 버스들이 k개 있고, 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 하나의 수직선 상의 두 교차점 사이 선분을 왕복 운행한다.

각 버스는 운행하는 선분 사이의 모든 교차점(선분의 양 끝 교차점 포함)에서 정차한다.

출발지 교차점과 목적지 교차점 (출발지와 목적지는 다름)이 주어질 때, 출발지에서 목적지로 버스만을 이용하여 가려고 한다.

이용하는 버스의 최소 수를 구하는 프로그램을 작성하시오.

예를 들어, 8대의 버스가 다음과 같이 운행한다고 하자. 1번 버스: (2, 1) - (2, 2)

2번 버스: (1, 1) - (5, 1)

3번 버스: (3, 2) - (6, 2)

4번 버스: (5, 6) - (5, 1)

5번 버스: (1, 5) - (7, 5)

6번 버스: (7, 3) - (7, 6)

7번 버스: (2, 1) - (2, 6)

8번 버스: (3, 5) - (6, 5)

출발지가 (2, 1)이고 목적지가 (7, 4)라 하자.

한 가지 방법으로, 처음에 2번 버스를 타고 교차점 (5, 1)에서 내려, 4번 버스를 타고 (5, 5)에서 내리고, 5번 버스를 탄 후 (7, 5)에서 내려, 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

그러면 이용하는 버스 수는 4이다.

다른 방법으로, 7번 버스를 타고 (2, 5)에서 내려, 5번 버스를 타고 (7, 5)에서 내린 후, 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

그러면 이용하는 버스 수는 3이고 이것이 최소이다.

입력 형식

첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다(1 ≤ m,n ≤ 100,000).

두 번째 줄에 버스의 수 (1≤k≤5,000)가 주어진다.

세 번째 줄부터 k줄에 걸쳐 각 줄에 버스의 운행구간을 나타내는 5개의 수 b, x1, y1, x2, y2가 빈칸을 사이에 두고 주어진다.

여기서 b(1≤b≤k)는 버스의 번호, (x1,y1)과 (x2,y2)는 이 버스가 운행하는 양쪽 끝 교차점의 좌표를 나타낸다.

마지막 줄에 출발지와 목적지 좌표를 나타내는 네 개의 수 sx, sy, dx, dy가 빈칸을 사이에 두고 주어진다.

여기서 (sx,sy)는 출발지 좌표이고 (dx,dy)는 목적지 좌표이다. 1≤x1, x2, sx, dx≤m이고, 1≤y1, y2, sy, dy≤n이다.

모든 입력에 대하여, 출발지와 목적지는 다르게 주어지며 출발지에서 목적지로 가는 방법은 한 가지 이상 존재한다.

<제약조건>

m 혹은 n이 1인 테스트데이터가 전체의 20%이다.

출력 형식

첫째 줄에 이용하는 최소 버스 수를 출력한다.

입력 예

7 6
8
1 2 1 2 2
2 1 1 5 1
6 7 3 7 6
7 2 1 2 6
3 3 2 6 2
4 5 6 5 1
5 1 5 7 5
8 3 5 6 5
2 1 7 4

출력 예

ChangeBus.h

#pragma once
#include <iostream>
#include <vector>
#include <queue>

#include "../../Base.h"

using std::vector;
using std::queue;

class ChangeBus : public Base
{
private:
	struct Point
	{
		Point() : x(0), y(0) {}
		Point(int x, int y) : x(x), y(y) {}

		int x;
		int y;

		friend std::istream& operator>>(std::istream& is, Point& p)
		{
			is >> p.x >> p.y;

			// (0, 0) 부터 시작하도록 보정
			p.x -= 1;
			p.y -= 1;

			return is;
		}
	};

	struct BusLine
	{
		enum class MoveDirection
		{
			None,
			Horizontal,
			Vertical
		};

		BusLine() : num(0), dir(MoveDirection::None), checked(false) {}

		int num;
		Point start;
		Point end;
		MoveDirection dir;
		bool checked;

		bool IsInWay(const Point& p) const
		{
			if (dir == MoveDirection::Horizontal)
			{
				if (p.y != start.y)
				{
					return false;
				}

				return start.x <= p.x && p.x <= end.x;
			}
			else
			{
				if (p.x != start.x)
				{
					return false;
				}

				return start.y <= p.y && p.y <= end.y;
			}
		}

		// s: 작은 값, e: 큰 값
		bool IsInWay(const int& s, const int& e)
		{
			if (dir == MoveDirection::Horizontal)
			{
				return !(e < start.x || end.x < s);
			}
			else
			{
				return !(e < start.y || end.y < s);
			}
		}

	private:
		void SwapStartEnd()
		{
			Point temp = start;
			start.x = end.x;
			start.y = end.y;
			end = temp;
		}
		
		friend std::istream& operator>>(std::istream& is, BusLine& bus)
		{
			is >> bus.num >> bus.start >> bus.end;

			if (bus.start.x != bus.end.x)
			{
				bus.dir = MoveDirection::Horizontal;
				if (bus.end.x < bus.start.x)
				{
					bus.SwapStartEnd();
				}
			}
			else
			{
				bus.dir = MoveDirection::Vertical;
				if (bus.end.y < bus.start.y)
				{
					bus.SwapStartEnd();
				}
			}

			return is;
		}
	};

	struct CheckInfo
	{
		CheckInfo(int busIdx, int cnt) : busIdx(busIdx), cnt(cnt) {}

		int busIdx;
		int cnt;
	};

protected:
	virtual void Code() override;

private:
	void Ready();
	void Finish();

	int GetLeastBusCnt();

private:
	int m, n;
	int k;
	Point ps, pe;
	vector<BusLine> busList;
	vector<vector<int>> horizontalBusList;
	vector<vector<int>> verticalBusList;
	queue<CheckInfo> q;
};

ChangeBus.cpp

void ChangeBus::Code()
{
	Ready();
	std::cout << GetLeastBusCnt();
	Finish();
}

void ChangeBus::Ready()
{
	std::cin >> n >> m;

	std::cin >> k;
	horizontalBusList.resize(m);
	verticalBusList.resize(n);
	for (int i = 0; i < k; i++)
	{
		busList.push_back(BusLine());
		std::cin >> busList[i];

		BusLine& curBus = busList[i];
		if (curBus.dir == BusLine::MoveDirection::Horizontal)
		{
			horizontalBusList[curBus.start.y].push_back(i);
		}
		else
		{
			verticalBusList[curBus.start.x].push_back(i);
		}
	}

	std::cin >> ps >> pe;

	// 시작 점을 지나는 버스를 다 체크해준다.
	for (int i = 0; i < k; i++)
	{
		if (busList[i].IsInWay(ps))
		{
			q.push(CheckInfo(i, 1));

			busList[i].checked = true;
		}
	}
}

void ChangeBus::Finish()
{
	busList.clear();
	horizontalBusList.clear();
	verticalBusList.clear();

	while (q.empty() == false)
	{
		q.pop();
	}
}

/// <summary>
/// 버스를 갈아타는 최소 횟수를 찾아 반환한다.
/// </summary>
/// <returns>버스 횟수</returns>
int ChangeBus::GetLeastBusCnt()
{
	int leastCnt{ 999'999'999 };

	while (q.empty() == false)
	{
		CheckInfo curInfo = q.front();
		q.pop();

		const BusLine& curBus = busList[curInfo.busIdx];
		if (curBus.IsInWay(pe))
		{
			if (curInfo.cnt < leastCnt)
			{
				leastCnt = curInfo.cnt;
			}

			break;
		}

		if (curBus.dir == BusLine::MoveDirection::Horizontal)
		{
			Point newPos;
			newPos.y = curBus.start.y;
			// 가로 이동 시 세로로 이동하는 버스는 다 체크
			for (newPos.x = curBus.start.x; newPos.x <= curBus.end.x; newPos.x++)
			{
				for (const int& verticalBusIdx : verticalBusList[newPos.x])
				{
					if (busList[verticalBusIdx].checked)
					{
						continue;
					}

					if (busList[verticalBusIdx].IsInWay(newPos))
					{
						q.push(CheckInfo(verticalBusIdx, curInfo.cnt + 1));
						busList[verticalBusIdx].checked = true;
					}
				}
			}
			// 가로 이동하는데 길 겹치는 거 체크
			for (const int& horizontalBusIdx : horizontalBusList[newPos.y])
			{
				if (busList[horizontalBusIdx].checked)
				{
					continue;
				}

				if (busList[horizontalBusIdx].IsInWay(curBus.start.x, curBus.end.x))
				{
					q.push(CheckInfo(horizontalBusIdx, curInfo.cnt + 1));
					busList[horizontalBusIdx].checked = true;
				}
			}
		}
		else
		{
			Point newPos;
			newPos.x = curBus.start.x;
			// 세로 이동 시 가로로 이동하는 버스는 다 체크
			for (newPos.y = curBus.start.y; newPos.y <= curBus.end.y; newPos.y++)
			{
				for (const int& horizontalBusIdx : horizontalBusList[newPos.y])
				{
					if (busList[horizontalBusIdx].checked)
					{
						continue;
					}

					if (busList[horizontalBusIdx].IsInWay(newPos))
					{
						q.push(CheckInfo(horizontalBusIdx, curInfo.cnt + 1));
						busList[horizontalBusIdx].checked = true;
					}
				}
			}
			// 세로 이동하는데 길 겹치는 거 체크
			for (const int& verticalBusIdx : verticalBusList[newPos.x])
			{
				if (busList[verticalBusIdx].checked)
				{
					continue;
				}

				if (busList[verticalBusIdx].IsInWay(curBus.start.y, curBus.end.y))
				{
					q.push(CheckInfo(verticalBusIdx, curInfo.cnt + 1));
					busList[verticalBusIdx].checked = true;
				}
			}
		}
	}

	return leastCnt;
}

실행 결과 Success(100)

※ 단순히 맵을 그리는 대신 속도를 늘리기 위한 방안을 고려해야 한다.

코드 해설

이 문제의 기본적인 구상은 단순하다.

길을 찾아 가는데, 길을 이동하는 횟수를 세는 게 아니라 이동하다 길을 바꿔가는(버스를 갈아타는) 회수를 찾는 것.

따라서 BFS로 이동하다 버스가 바뀔 때를 체크해서 회수를 증가시키면 된다.

이를 위해서 먼저, 중복해서 버스를 바꾸지 않도록 체크할 수 있는 플래그가 하나 있어야 한다.

나는 이를 위해 버스 정보를 받는 구조체 안에 내가 이 버스를 탄 적 있는지 체크하기 위한 checked 변수를 넣었다.

	struct BusLine
	{
		enum class MoveDirection
		{
			None,
			Horizontal,
			Vertical
		};

		BusLine() : num(0), dir(MoveDirection::None), checked(false) {}

		int num;
		Point start;
		Point end;
		MoveDirection dir;
		bool checked;

이것을 통해 반복문을 여러번 돌지 않고 중단할 수 있도록 막을 수 있게 된다.

			for (newPos.x = curBus.start.x; newPos.x <= curBus.end.x; newPos.x++)
			{
				for (const int& verticalBusIdx : verticalBusList[newPos.x])
				{
					if (busList[verticalBusIdx].checked)
					{
						continue;
					}

그리고 버스의 개수가 늘어나면 하나의 리스트를 돌면서 확인하는 것은 굉장히 느려진다.

따라서 이를 방지하기 위해 리스트를 버스 방향에 따라 가로, 세로로 나눠야 한다.

이때, 버스는 가로나 세로 방향으로 일직선으로 이동하므로 x나 y는 고정되어 있게 된다.

따라서 고정된 x나 y를 기준으로 리스트를 나누고 거기에 버스 인덱스를 넣어주면 추후 같은 x, y를 쓰는 버스를 검사할 때 범위만 체크하면 되는 상태가 된다.

대충 가로로 가는 빨간 버스가 이렇게 있을 때 y = 1인 리스트에 버스 인덱스를 저장한다.

마찬가지로 파란색 은 x = 2인 리스트에 인덱스를 저장해 둔다.

	horizontalBusList.resize(m);
	verticalBusList.resize(n);
	for (int i = 0; i < k; i++)
	{
		busList.push_back(BusLine());
		std::cin >> busList[i];

		BusLine& curBus = busList[i];
		if (curBus.dir == BusLine::MoveDirection::Horizontal)
		{
			horizontalBusList[curBus.start.y].push_back(i);
		}
		else
		{
			verticalBusList[curBus.start.x].push_back(i);
		}
	}

이를 버스를 이동하면서 가로로 가는 버스는 y가 고정이므로 y가 같은 버스 인덱스를 꺼내 현재 버스의 이동 범위에 들어가는지 체크해서 경로를 바꿔준다.

			// 가로 이동 시 세로로 이동하는 버스는 다 체크
			for (newPos.x = curBus.start.x; newPos.x <= curBus.end.x; newPos.x++)
			{
				for (const int& verticalBusIdx : verticalBusList[newPos.x])
				{
					if (busList[verticalBusIdx].checked)
					{
						continue;
					}

					if (busList[verticalBusIdx].IsInWay(newPos))
					{
						q.push(CheckInfo(verticalBusIdx, curInfo.cnt + 1));
						busList[verticalBusIdx].checked = true;
					}
				}
			}

그리고 가로로 이동하는 버스라도 범위가 겹쳐서 갈아탈 수 있는 가로 버스가 있을 수 있으므로 범위가 겹치는지 검사하여 이것도 경로에 넣어준다.

			// 가로 이동하는데 길 겹치는 거 체크
			for (const int& horizontalBusIdx : horizontalBusList[newPos.y])
			{
				if (busList[horizontalBusIdx].checked)
				{
					continue;
				}

				if (busList[horizontalBusIdx].IsInWay(curBus.start.x, curBus.end.x))
				{
					q.push(CheckInfo(horizontalBusIdx, curInfo.cnt + 1));
					busList[horizontalBusIdx].checked = true;
				}
			}

그리고 이 것을 세로로 이동하는 버스에 대해서도 반복해 주면 된다.

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.

github.com

문제출처

버스 갈아타기 - Jungol

undefined - Jungol

www.jungol.co.kr

저작자표시 비영리 변경금지

ABOUT ME

코딩시간 코딩시간

Intermediate_Coder/그래프탐색-BFS/버스 갈아타기

코드 해설

문제출처

티스토리툴바

ABOUT ME

Intermediate_Coder/그래프탐색-BFS/버스 갈아타기

코드 해설

문제출처

관련글 관련글 더보기

티스토리툴바