2105번 디저트 카페

어려웠던 문제였다

단순 BFS 문제인줄 알고, BFS로 접근하였다가 아닌 것 같아서 바로 다른 풀이를 생각해보려 하였으나, 

잘 떠오르지가 않았다.

그래서 다른 분의 코드를 참고하였다. 풀이 ebook도 참고하였다.

백트래킹 문제인줄은 몰랐다.

열심히 공부해야겠다.

문제 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

풀이 : https://www.swexpertacademy.com/main/learn/course/lectureHtmlViewer.do

<백트래킹>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[21][21] = { 0, };
 
int N = 0;
 
int result = -1;
 
int dy[4] = { 1, 1, -1, -1 };
int dx[4] = { 1, -1, -1, 1 };
 
bool visit[101] = { false, };
 
int sy = 0, sx = 0; // 시작 점
 
void DFS(int row, int column, int pos, int Count)
{
    int y = row + dy[pos];
    int x = column + dx[pos];
 
    if (pos == 3 && y == sy && x == sx)
    {
        // pos가 3이라는 뜻은, 0부터 시작한 pos가 한 바퀴 다 돌았다는 뜻
        result = max(result, Count);
 
        return;
    }
 
    if (0 <= y && y < N && 0 <= x && x < N && !visit[map[y][x]]) // 방문하지 않았던 곳이어야만 함
    {
        visit[map[y][x]] = true;
 
        DFS(y, x, pos, Count + 1); // 방향 전환 없이 쭉 간다
 
        if (pos < 3)
        {
            // 위에서 방향 전환 없이 쭉 가다가, 
            // 그 함수가 끝나면(갈 수 있는 곳 까지 갔다면) 이제는 방향 전환을 해야한다.
 
            DFS(y, x, pos + 1, Count + 1); 
            // pos가 3 미만 이라는 뜻은 아직 원래 출발점으로 도달하지 않았다는 뜻
        }
 
        visit[map[y][x]] = false; // 다음 진행을 위해, 다시 false로 바꿔준다.
    }
}
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                sy = i;
                sx = j;
 
                visit[map[i][j]] = true;
 
                // 길이에 그 자신도 포함이므로, Count는 1부터 시작
                DFS(i, j, 0, 1); 
 
                visit[map[i][j]] = false; // 다음 진행을 위해 false로 바꿔준다.
            }
        }
 
        printf("#%d %d\n", tc, result);
 
        result = -1;
    }
 
    return 0;
}

<단순 구현>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[21][21] = { 0, };
 
int N = 0;
 
int result = -1;
 
int dy[4] = { 1, 1, -1, -1 };
int dx[4] = { 1, -1, -1, 1 };
 
bool visit[101] = { false, };
 
int sy = 0, sx = 0; // 시작 점
 
void solve()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int a = 1; a < N; a++)
            {
                for (int b = 1; b < N; b++)
                {
 
                    if (j + a < N            // 오른쪽 범위
                        && i + a + b <N        // 아래 범위
                        && j - b >= 0        // 왼쪽 범위
                        && 2 * (a + b) > result) // 이전에 구했던 값보다 크다면
                    {
                        memset(visit, false, sizeof(visit));
 
                        bool stop = false;
 
                        int curi = i, curj = j;
 
                        // 우측 하단
                        for (int n = 0; n < a; n++)
                        {
                            ++curi; ++curj;
 
                            if (!visit[map[curi][curj]]) visit[map[curi][curj]] = true;
                            else stop = true;
                        }
                        
                        if (stop) continue;
 
 
                        // 좌측 하단
                        for (int n = 0; n < b; n++)
                        {
                            ++curi; --curj;
 
                            if (!visit[map[curi][curj]]) visit[map[curi][curj]] = true;
                            else stop = true;
                        }
 
                        if (stop) continue;
 
                        // 좌측 상단
                        for (int n = 0; n < a; n++)
                        {
                            --curi; --curj;
 
                            if (!visit[map[curi][curj]]) visit[map[curi][curj]] = true;
                            else stop = true;
                        }
 
                        if (stop) continue;
 
 
                        // 우측 상단
                        for (int n = 0; n < b; n++)
                        {
                            --curi; ++curj;
 
                            if (!visit[map[curi][curj]]) visit[map[curi][curj]] = true;
                            else stop = true;
                        }
 
                        if (stop) continue;
 
                        result = 2 * (a + b);
                    }
                }
            }
        }
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        solve();
 
        printf("#%d %d\n", tc, result);
 
        result = -1;
    }
 
    return 0;
}