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

"나의 아픈손가락이 되어 버린 문제..."

 

     [문제 설명]

 출제자는 디저트 투어를 할 계획이다. 원 안의 숫자는 디저트의 종류를 의미하고,

카페들 사이에는 대각선으로 이동가능한 길들이 존재한다.

디저트 투어는 한 카페에서 출발하여 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.

 

그 뿐만 아니라, 도중에 먹었던 디저트를 팔았던 카페에 다시 방문해서는 안된다.

 

추가조건:  (1) 하나의 카페에서만 먹으면 안된다.

                    (2) 왔던 길을 다시 되돌아 가면 안된다.

 

'디저트를 가장 많이 먹을 수 있는 경로를 찾고 그 떄의 디저트의 수를 출력하는 프로그램을 작성하시오'

 

[문제 풀이]

 

1. 백트래킹

 

 백트래킹을 구현 하기에 앞서서 분기 조건을 생각해보자.

 

(1) 이미 먹었던 종류의 디저트가 존재하는 카페는 가지 않는다.

(2) 해당 지역을 벗어날 수 없다.

(3) 출발했던 장소에 다시 도착해야 경로가 완성된다.

 

 

 해당 진행 방향을 기준으로 대각선으로 이동하기로 정하고

수형도를 작성하여 보았다.

 

"재귀함수가 익숙하지 않다면 무조건 무조건 수형도를 그려보자"

 

 수형도에 그려진 그대로 재귀함수를 구현하면 되는 어렵지 않은 문제다.

 

물론 재귀함수를 구현하는 게 쉽지 않다. 머릿속으로 탁 재귀함수를 짜낼수 있다면 정말 좋겠지만, 그게 아니라면

수형도를 그려서 천천히 해보는 게 차라리 문제를 빨리 푸는 길이다.

#include <bits/stdc++.h>
using namespace std;
int N, T;
int A[20][20];
int dy[] = { 1,1,-1,-1 };
int dx[] = { 1,-1,-1,1 };
bool used[101];
int ans;
int sy, sx;

bool oob(int y, int x)
{
	return y < 0 || y >= N || x < 0 || x >= N;
}

void go(int y, int x, int dir, int count)
{
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	if (dir == 3 && ny == sy && nx == sx)
	{
		ans = max(ans, count);
		return;
	}
	if (oob(ny, nx) || used[A[ny][nx]]) return;
	used[A[ny][nx]] = true;
	go(ny, nx, dir, count + 1);
	if (dir < 3) go(ny, nx, dir + 1, count + 1);
	used[A[ny][nx]] = false;
}

int main()
{
	scanf("%d", &T);
	for (int t = 0; t < T; t++)
	{
		ans = -1;
		scanf("%d", &N);
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &A[i][j]);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				sy = i,sx = j;
				used[A[i][j]] = true;
				go(i, j, 0, 1);
				used[A[i][j]] = false;
			}
		}
		printf("#%d %d\n", t + 1, ans);
	}
	return 0;
}

 2019년 하반기 삼성 sw역량 테스트에서 이 문제랑 굉장히 유사한 문제가 나왔었는데, 

그 문제도 위 문제 처럼 마름모 꼴로 다시 원위치(좌표)로 돌아오는 구역을 나누는 문제였다.

보자 마자 이 문제가 생각이 나서 재귀로 마름모꼴 구현해놓고 구역 나누다가 안되서 포기하고,

재귀+for문으로 어찌저찌 풀려다가 못 풀고 나온 문제다.

그 때 이 문제가 생각안났다면 나는 어떤 방법으로 접근하려고 했을까... 아무쪼록 내 아픈 손가락이 되어버린 문제...