[모의 SW 역량테스트 - 2105] 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE

SW Expert Academy

 

SW Expert Academy 사이트에 로그인 하면 위 링크로 접속해서 문제를 볼 수 있습니다.

 

개인적으로 이런 류의 문제는 조금 당황스러웠다.

 

사실 처리해줘야 할 것들은 별로 없지만 대각선 이동이라는 문제가 평소와는 다르게 신선(?)하게 다가왔다.

 

한 번 풀어봤던 문제임에도 불구하고 꽤 많은 시간이 걸렸으며 좀 더 공부를 해야겠다는 생각이 들었다.

 

이 문제는 처음에 어떻게 접근해야할지 생각만 해낸다면 구현하는데 큰 어려움을 겪을 만한 문제는 아니었다.

 

출발지점으로 다시 도착했을 때 먹은 디저트의 갯수를 세면 되는 문제인데,

 

나같은 경우는 다시 원위치로 도착했을 경우를 좌표가 같을 경우로 설정해서 답을 구했다.

 

여기서 주의할 점은 디저트를 먹고 지나가는 경로가 직사각형 or 정사각형을 이뤄야 하기 때문에 이걸 유지할 수 있도록 해줘야 한다.

 

나는 여기서 사각형은 꼭지점이 4개니까 각 방향을 돌 때(이전에 진행했던 방향과 다를 때) 꼭지점이 생기기 때문에 이 경우를 카운트 해줬고 이 카운트 변수가 4 이상이 된다면 사각형이 만들어 졌을거라고 인식하고 dfs 탐색을 종료시켰다.

 

- 풀이 방법

1. 입력을 받는다.

 

2. 모든 좌표에 대해 dfs 탐색을 시작한다.

 

3. dfs 탐색에서 return의 조건을 만들어준다.

(저는 다음 이동해야할 좌표가 원래 위치로 돌아왔을 때의 좌표일 경우 결과값을 갱신하고 return 시켰습니다.)

 

4. return 조건이 아닐 경우 4방향으로 탐색해준다.(대각선으로)

 

5. 탐색을 하는데 먹었던 desert를 또 먹지 않기 위해 desert라는 일차원 배열을 만들어줬고 desert의 값이 0이 아닐 경우는 이미 먹었던 디저트이기 때문에 다음에 이동하지 않도록 했다.

 

6. 가장 중요한 coner라는 변수를 만들고 이 변수가 4 이상일 경우 직사각형이 만들어졌다는 뜻이므로 dfs 탐색을 종료하게 했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>

using namespace std;

int t, n, res;
int map[21][21];
int visited[21][21];
int desert[101];
const int dy[] = { -1,-1,1,1 };
const int dx[] = { -1,1,-1,1 };

void dfs(int u, int v, int fy, int fx, int before, int len, int coner) {

	if (coner >= 4) return;

	if (u == fy && v == fx && len >= 4) {
		if (len > res) res = len;

		return;
	}

	for (int dir = 0; dir < 4; dir++) {

		int ny = u + dy[dir];
		int nx = v + dx[dir];

		if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

		if (desert[map[ny][nx]] == 0 && visited[ny][nx] == 0) {
			visited[ny][nx] = 1;
			desert[map[ny][nx]] = 1;
			if (before != dir) {
				dfs(ny, nx, fy, fx, dir, len + 1, coner + 1);
			}
			else dfs(ny, nx, fy, fx, dir, len + 1, coner);
			visited[ny][nx] = 0;
			desert[map[ny][nx]] = 0;
		}
	}
}

int main(void) {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {
		res = 0;

		scanf("%d", &n);

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				scanf("%d", &map[y][x]);
			}
		}

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				dfs(y, x, y, x, 0, 0, 0);
			}
		}
		if (res == 0) res = -1;
		printf("#%d %d\n", tc, res);
	}


	getchar();
	getchar();

	return 0;
}