SWEA 2105번 [모의 SW 역량테스트] 디저트 카페 C+ DFS, 브루트포스 알고리즘

리뷰

DFS와 브루트포스 알고리즘이 접목된 문제

문제 풀이

1. 배열을 초기화 해줘야 한다. 각 테케의 데이터를 1 ~ N로 받고 나머지는 -1로 초기화 해준다.
2. 출발한 카페로 돌아와야 하니 각 DFS를 실행할때 현재 위치의 좌하 방향의 좌표를 도착지로 설정해 준다.
3. 경로상에 같은 카페가 있으면 안되니 방문 처리를 해줘야 한다. 방문한 좌표의 값을 v배열의 인덱스로 방문처리
4. 지나온 길에 대한 정보를 기억해야 한다. path 벡터에 기록해 준다. (길이를 구하는 문제이니 아무 값이나 들어와도 상관x)
5. 도착지에 도달했을 경우 path벡터의 길이가 방문한 카페의 길이가 된다. 최대값을 ans변수에 기록해 준다.
6. 모든 좌표에 대한 DFS가 종료된 경우 ans의 값이 4보다 작으면 -1로 변경 (완벽한 사각형이 만들에 진게 아니다.)
7. 각 테스트 케이스에 대하여 ans값을 출력 시켜준다.

 

참고 사항

요구 사항

1. 대각선 방향으로 움직인다.
2. 출발한 카페로 돌아와야 한다.
3. 경로상에 같은 카페(동일한 숫자)가 있으면 안된다.
4. 맵을 벗어나면 안된다.
5. 방문한 디저트 카페들의 값의 합이 가장 큰 경로를 찾으면 된다.

진행 방식

 - 방향

1. 대각선으로 그대로 갈 것인가?
2. 꺾어서 갈 것인가?

 - DFS

1. 모든 경로 탐색 필요(가장 많은 디저트 카페를 찾아야 함)
2. N의 범위가 20 ~ 30정도에 해당할 경우 백트래킹을 통해 탐색 한다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int t, n;
int m[30][30];
int v[101];
int destRow, destCol;
vector<int> path;
int ans;

// 우하 좌하 좌상 우상
int dr[] = { -1, -1, 1, 1 };
int dc[] = { 1, -1, -1, 1 };

void init() {
	ans = 0;
	path.clear();
	for (int i = 0; i < 30; i++) {
		for (int j = 0; j < 30; j++) {
			m[i][j] = -1;
		}
	}
	for (int i = 0; i < 101; i++) {
		v[i] = 0;
	}
}

void input() {
	cin >> n;
	for (int i = 1; i <= n; i++) { // for문의 범위 : 1 ~ n까지, 경로를 벗어날 경우 쉽게 처리하기 위함
		for (int j = 1; j <= n; j++) {
			cin >> m[i][j];
		}
	}
}

void dfs(int row, int col, int dir) { // 현재 좌표와 방향 정보를 받기
	// 기저 조건
	if (row == destRow && col == destCol) {
		if (ans < path.size()) {
			ans = path.size();
		}
		return;
	}
	for (int ndir = dir; ndir <= dir + 1; ndir++) {
		if (ndir >= 4) continue;
		int nr = row + dr[ndir], nc = col + dc[ndir];
		if (v[m[nr][nc]] == 1) continue;
		if (m[nr][nc] == -1) continue;		
		v[m[nr][nc]] = 1; // index : 카페 번호 value : 경로 상에 같은 카페가 있는가?
		path.push_back(m[nr][nc]);
		dfs(nr, nc, ndir); // 재귀 호출(다음 좌표와 방향 정보를 주기)
		path.pop_back();
		v[m[nr][nc]] = 0; // 원복
	}
}

void solution() {
	// 모두 DFS 돌려보기
	for (int row = 1; row <= n; row++) {
		for (int col = 1; col <= n; col++) {
			// 도착지 설정 필요
			destRow = row + 1; destCol = col - 1;
			// 시작점 세팅
			v[m[row][col]] = 1;
			path.push_back(m[row][col]);
			dfs(row, col, 0);
			path.pop_back();
			v[m[row][col]] = 0;
		}
	}
	if (ans < 4) ans = -1;
}

int main() {
	cin >> t;
	for (int c = 1; c <= t; c++) {
		init();
		input();
		solution();
		cout << "#" << c << " " << ans << "\n";
	}
}