[G4] 백준 16432번 떡장수와 호랑이 C++ DFS, DP

리뷰

 

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

깊이 우선 탐색과 메모제이션을 활용해 푸는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• flag : 최적 경로를 찾았는지 여부를 저장할 변수
• edges : 간선 정보를 저장할 벡터 배열
• v : 이미 방문한 상황인지 여부를 체크하기 위한 2차원 배열

 

함수

1. dfs

void dfs( int level, vector<int>& stack )
{
	if ( flag )
		return;

	if ( level == n )
	{
		flag = true;

		for ( int i : stack )
			cout << i << '\n';

		return;
	}

	int last = stack.empty() ? 0 : stack.back();

	if ( v[ level ][ last ] )
		return;

	for ( int i : edges[ level ] )
	{
		if ( !stack.empty() && stack.back() == i )
			continue;

		stack.push_back( i );
		dfs( level + 1, stack );
		stack.pop_back();

		if ( flag )
			return;
	}

	v[ level ][ last ] = true;
}

 

n까지 도달 가능한 최적의 경로를 찾기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n개의 날에 가진 떡을 입력 받아 edges를 초기화한다.
2. 정수형 벡터 stack을 초기화 하고, dfs함수에 0, stack을 인자로 전달하여 호출한다.
3. dfs내부에선 변수 levle, stack에 매개변수를 받는다.
4. 첫 번째 기저 조건으로 flag가 true라면 이미 최적 경로를 찾은 것이므로 return처리한다.
5. 두 번째 기저 조건으로 level이 n에 도달한 경우 최적 경로를 찾은 것이므로 flag를 true로 저장한다.
6. stack을 순회하며 각 요소를 줄바꿈을 기준으로 출력하고, return처리한다.
7. 변수 last에 stack의 마지막 요소를 저장한다, 비어있다면 0으로 저장한다.
8. 세 번째 기저 조건으로 v[level][last]가 true일 경우 이미 방문한 경로이므로 return처리한다.
9. edges[level]을 순회하며, 만약 stack이 비었거나, stack의 마지막 요소가 동일하다면 continue처리한다.
10. stack에 현재 요소를 push하고, 재귀 단계를 높여 dfs함수를 호출한다.
11. 재귀를 마친 후엔 stack의 마지막 요소를 pop해준다.
12. 만약 flag가 true일 경우 for문을 더 이상 순회하지 않고 return처리한다.
13. 블록이 종료되기 전에 v[level][last]를 true로 처리한다.
14. dfs함수가 종료된 후에도 flag가 false상태라면 -1을 출력한다.

 

트러블 슈팅

1. 메모제이션을 하지 않고 일반적인 dfs를 구현하였더니 바로 시간 초과를 받았다.
2. 핵심은 이미 왔던 경로, 즉 이미 실패한 경험이 있는 경로는 탐색을 수행하지 않는 것이다.

 

참고 사항

1. 방법이 여러 가지인 경우 그 중 하나만 출력한다.

 

정답 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1000;
int n;
bool flag;
vector<int> edges[ N ];
bool v[ N ][ 10 ];

void dfs( int level, vector<int>& stack )
{
	if ( flag )
		return;

	if ( level == n )
	{
		flag = true;

		for ( int i : stack )
			cout << i << '\n';

		return;
	}

	int last = stack.empty() ? 0 : stack.back();

	if ( v[ level ][ last ] )
		return;

	for ( int i : edges[ level ] )
	{
		if ( !stack.empty() && stack.back() == i )
			continue;

		stack.push_back( i );
		dfs( level + 1, stack );
		stack.pop_back();

		if ( flag )
			return;
	}

	v[ level ][ last ] = true;
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );
	cout.tie( 0 );

	cin >> n;
	for ( int i = 0; i < n; ++i )
	{
		int m; cin >> m;
		while ( m-- )
		{
			int d; cin >> d;
			edges[ i ].push_back( d );
		}
	}

	vector<int> stack;
	dfs( 0, stack );

	if ( !flag )
		cout << -1;
}