JUNGOL/Intermediate_Coder/그래프탐색-DFS/1912 : 미로 탐색

Intermediate_Coder/그래프탐색-DFS/미로 탐색

---

문제                                            

동현이는 방이 N개인 미로의 지도를 갖고 있다.

각 방에는 1번부터 N번까지 번호가 매겨져 있고, N개의 방 사이에는 M개의 문이 있으며, 

각 문은 서로 다른 두 방을 연결한다. 

동현이는 1번 방에서 출발해서 N개의 방을 모두 탐색해 볼 것이다.

 

동현이는 모험심이 강하기 때문에 항상 새로운 방을 찾기를 원한다. 

동현이는 자신이 위치한 방과 연결된 방 중 한 번도 들르지 않은 방이 있다면 그 중 가장 번호가 작은 방으로 가고, 

그렇지 않으면(연결된 방이 모두 전에 들렀던 방이면) 그냥 왔던 곳으로 되돌아가게 된다.

 

동현이가 N개의 방을 모두 방문하고 1번 방으로 오면 동현이는 탐색을 끝낸다. 

N개의 방을, 동현이가 먼저 방문한 순으로 정렬하는 프로그램을 작성하여라.

 

입력 형식                                     

첫 번째 줄에는 방의 수 N과 문의 수 M이 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000)

두 번째 줄부터 M개의 줄에는 각 문이 연결하는 두 방의 번호가 입력된다. 

모든 방들은 문을 통해 연결되어 있고, 임의의 두 방 사이에는 최대 1개의 문이 있다. 

전체 데이터의 38%는 2 ≤ N ≤ 3,000 이다.

 

출력 형식                                     

첫 번째 줄에 동현이가 방문한 순서대로 N개의 방의 번호를 정렬하여 출력한다.

 

입력 예                                        

5 6
1 3
3 4
4 2
2 1
1 4
4 5

 

출력 예                                        

1 2 4 3 5

 

Hint!

위 예제에 대한 미로의 지도는 다음과 같다.

JUNGOL 미로탐색

이 때, 동현이는 1→2→4→3→4→5→4→2→1 순으로 미로를 탐색하게 된다.

---

MazeExploration.h

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using std::vector;
using std::stack;

class MazeExploration : public Base
{
private:
	struct Room
	{
		Room(int roomNumber) : roomNumber(roomNumber), visited(false) {}

		int roomNumber;
		bool visited;
		vector<int> linkedRooms;
	};

	void FindRoomOrder(vector<Room> rooms, int n, vector<int>& roomOrder);
};

 

MazeExploration.cpp

void MazeExploration::Code()
{
	int n, m;
	std::cin >> n >> m;

	vector<Room> rooms;
	for (int i = 0; i <= n; i++)
	{
		rooms.push_back(Room(i));
	}

	int from, to;
	for (int i = 0; i < m; i++)
	{
		std::cin >> from >> to;
		rooms[from].linkedRooms.push_back(to);
		rooms[to].linkedRooms.push_back(from);
	}

	for (int i = 1; i <= n; i++)
	{
		std::sort(rooms[i].linkedRooms.begin(), rooms[i].linkedRooms.end());
	}

	vector<int> roomOrder;
	FindRoomOrder(rooms, n, roomOrder);

	for (int d : roomOrder)
	{
		std::cout << d << ' ';
	}
}

/// <summary>
/// 방의 방문 순서를 찾는다.
/// </summary>
/// <param name="rooms">방 정보</param>
/// <param name="n">방의 개수</param>
/// <param name="roomOrder">방문한 방 순서</param>
void MazeExploration::FindRoomOrder(vector<Room> rooms, int n, vector<int>& roomOrder)
{
	stack<int> s;
	int curRoom{ 1 };

	while (true)
	{
		if (!rooms[curRoom].visited)
		{
			rooms[curRoom].visited = true;
			roomOrder.push_back(rooms[curRoom].roomNumber);

			if (static_cast<int>(roomOrder.size()) == n)
			{
				break;
			}
		}

		bool hasValidRoom{ false };
		for (int linkedRoomNumber : rooms[curRoom].linkedRooms)
		{
			if (!rooms[linkedRoomNumber].visited)
			{
				s.push(curRoom);
				curRoom = linkedRoomNumber;
				hasValidRoom = true;
				break;
			}
		}

		if (!hasValidRoom)
		{
			curRoom = s.top();
			s.pop();
		}
	}
}

 

---

실행 결과 Success(100)

---

 

코드해설

먼저, 각 방에 연결된 문을 저장하기 위해 벡터를 포함하는 Room 구조체를 만든다.

	struct Room
	{
		Room(int roomNumber) : roomNumber(roomNumber), visited(false) {}

		int roomNumber;
		bool visited;
		vector<int> linkedRooms;
	};

 

연결된 방의 문의 경우엔 1 -> 2의 입력인 경우 1에 2를 추가하고 2에도 1을 추가해 줘야 한다.

	int from, to;
	for (int i = 0; i < m; i++)
	{
		std::cin >> from >> to;
		rooms[from].linkedRooms.push_back(to);
		rooms[to].linkedRooms.push_back(from);
	}

 

방을 찾다가 더 이상 갈 수 없는 경우 직전에 방문한 방으로 돌아가야 하므로 방에 방문한 경우 스택에 순서대로 저장한다.

		bool hasValidRoom{ false };
		for (int linkedRoomNumber : rooms[curRoom].linkedRooms)
		{
			if (!rooms[linkedRoomNumber].visited)
			{
				s.push(curRoom);
				curRoom = linkedRoomNumber;
				hasValidRoom = true;
				break;
			}
		}

 

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

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/그래프탐색-DFS/미로 탐색-JUNGOL