[알고리즘] 정올 1912 번 문제 : 미로 탐색

이번에는 그래프 탐색에 대한 알고리즘 문제를 소개합니다.

 

#1 문제 이해

문제 제목과 같이 미로 탐색 문제이고  모든 방을 탐색하고 방문한 순서대로 출력하는 문제입니다.

입력은 미로 형태이지만, 각 노드를 방문하는 형식이 될 것 같습니다.

 

문제는 아래에서 확인하시고 충분히 읽어보시길 바랍니다.

정올 1912번 문제

JUNGOL

 

#2 입력 방식 확인

입력된 미로 정보는 연결되는 방의 정보를 나타내는데, 문제에 나와있듯이 출발은 1번이다.

5 6  //! 방의 수 N:5, 문의 수 M:6
1 3  //! 각 문이 연결하는 두 방의 번호 1 <-> 3
3 4
4 2
2 1
1 4
4 5  //! 문의 수 M:6 만큼의 두 방의 번호가 입력

 

#3 그래프 그려보기

입력데이터는 다음과 같은 그래프가 될 것입니다.

 

#4 전역변수 선언

입력받은 데이터를 방(Node)과 문(Edge,간선) 형태의 그래프로 처리하기 위해서는 연속된 데이터를 처리할 수 있고 탐색을 할 수 있어야 겠습니다.

※ 반드시 전역변수를 선언할 필요는 없지만, 문제 풀이시 편의를 위해 전역으로 선언하겠습니다.

#include <iostream>
#include <cstdio>        //! C언어 표준 입출력
#include <vector>        //! vector 사용을 위해 추가
#include <stack>         //! stack 사용을 위해 추가

const int MAX = 1000000; //! #define 대신 상수(const)형태의 변수 선언

vector <int> room[MAX];  //! 각 방(Node)을 의미하는 vector 선언
int visit[MAX];          //! 방문여부를 기록하기 위한 배열 선언, index 가 방 번호가 된다.
stack <int> myStack;     //! stack 을 이용한 DFS(깊이 우선 탐색) 를 사용한다.

 

#5 데이터 입력받기

테스트를 위해서 아래 구문을 추가하면, txt file 형태로 input 을 처리할 수 있습니다.

freopen("input.txt", "r", stdin);

두 개의 방(노드)에 대해서 Vector 형태로 선언하여 양방향으로 저장하고, visit[ ](방문 표시 배열)  을 초기화 합니다.

	int n, m, a, b;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)	{
		scanf("%d %d", &a, &b);
		room[a].push_back(b);
		room[b].push_back(a);

		visit[i] = 0;
	}

 

#6 새로운 방 탐색

연결된 방 중 가장 번호가 작은 방부터 먼저 탐색하고 끝까지 탐색하면 다시 되돌아 온다(깊이 우선 탐색)

 

1. 탐색할 방을 Stack 에 Push 하고 방문을 기록한다.

2. 현재 탐색 중인 방과 연결된 곳중 가장 작은 곳을 찾아 다음 방문지로 지정한다.

3. 다음 방문지가 있다면, #1번을 반복하고 없다면, 빠져나온다(Pop)

 

코드는 더보기 ↓클릭↓

void DFS(int nRoom)
{
	myStack.push(nRoom);                  //! 탐색할 방은 Stack 에 Push 한다.
	printf("%d ", nRoom);
	visit[nRoom] = 1;                     //! 방문을 기록한다.

	while (!myStack.empty()) {
		int next = 9999999;
		int v = myStack.top();            //! v : 현재 탐색중인 방

		//! Find Next from Not visited room. 
		for (int i = 0; i < (int)room[v].size(); i++) {
			int findRoom = room[v][i];    //! room[v][i] 현재 탐색중인 방(v)의 i번째 연결을 의미
			if (0 == visit[findRoom]) {   //! 방문을 하지 않은 방이라면,
				if (findRoom < next) {    //! next(방문예정) 보다 작을 경우,
					next = findRoom;      //! next 교체 업데이트
				}
			}
		}
        
		if (9999999 == next) { //! Not next
			myStack.pop();
		}
		else
		{
			myStack.push(next);
			printf("%d ", next); //! 방문을 기록하는 시점에 출력
			visit[next] = 1;     //! 방문을 기록
		}
	}
}

 

이 문제는 여기까지 정리를 해보겠습니다.

※ 전체 코드를 추가해놓지 않았습니다. 한번 풀어보시고 필요하시면 댓글로 문의 주세요.