격자판에_숫자_이어_붙이기

SW Expert D4 문제 격자판에 숫자 이어 붙이기 문제
4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

Input:

1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1

Output:
#1 23

위와 같은 문제를 풀었다.
Set을 이용하면 쉽게 풀 수 있다.
Global 변수를 쓰지 않기 위해, 최대한 Parameter로 변수 및 Container를 넘겨주고자 했다.

Header는 무난하게 아래와 같이 작성했다. Direction은 그냥 동서남북을 그냥 이렇게 pair list로 저장했다.

#include <iostream>
#include <set>
#include <string>
using namespace std;
pair<int, int> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //to check adjcent

나는 주로 Boundary를 위해 Padding하는 것을 좋아한다. 원래 음수 양수로 나누기 위해 -1로 padding 했는데, 나중에 까먹고 다시 boundary를 잡았따. 뭐 딱히 상관은 없다
아래는 check으로 잡았다. 솔직히 Memoization을 이용할까 생각했는데, 1~6개의 숫자를 모두 저장하는게 까다롭기도 하고,
생각해보면 4방향을 7자리는 대략 4^7이고 2^14 이니 대충 만 정도니까 2초면 시간이 펑펑 남겠구나 생각해 그냥 return만 잘 써주기로 했다
(length == 7 이때 return을 안해줘서 10분 정도 헤맸다 ㅋㅋ st를 cout찍어보니 한 100자리씩 찍히길래 롸?? 하고 고쳤다 ㅋㅋ)

void check(int **array, int i, int j, string st, set<string> *set_name)
{
    if (i == 0 || i == 5 || j == 0 || j == 5) //out of boundary
        return;
    st = st + to_string(array[i][j]);
    if (st.length() == 7) //found seven
    {
        set_name->insert(st);
        return;
    }
    for (int k = 0; k < 4; k++)
        check(array, i + directions[k].first, j + directions[k].second, st, set_name);
}

다른 사람들은 Set을 초기화 안해서 시간을 날렸다고 한다. 아마 Global로 짜서 그렇겠지.
나는 다행히 test_case for문 안에다가 선언해서 신경 안써도 됐다.
Easy

int main(int argc, char **argv)
{
    int sum = 0;
    int test_case;
    int T;
    cin >> T;
    int **arr = new int *[6];
    for (int i = 0; i < 6; i++)
        arr[i] = new int[6];
    for (test_case = 1; test_case <= T; ++test_case)
    {
        set<string> ans;
        //input with padding -1
        for (int i = 0; i < 6; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                if (i == 0 || i == 5 || j == 0 || j == 5)
                    arr[i][j] = -1;
                else
                    cin >> arr[i][j];
            }
        }
        //do I need memoization? I don't think so
        for (int i = 1; i < 5; i++)
            for (int j = 1; j < 5; j++)
                check(arr, i, j, "", &ans);
        cout << "#" << test_case << " " << ans.size() << endl;
    }
    for (int i = 0; i < 6; i++)
        delete[] arr[i];
    delete[] arr;
    return 0; //정상종료시 반드시 0을 리턴해야합니다.
}

B