[SWA] 2819. 격자판의 숫자 이어 붙이기

2819. 격자판의 숫자 이어 붙이기

4x4 크기의 격자 판에 숫자가 주어 지는데, 임의의 위치에서 정확히 6번 움직여 주어진 숫자를 이어 붙여 만들어진 서로 다른 7자리 숫자의 개수를 구하는 문제이다.

0이 맨 앞에 들어가도 자리수에 포함한다. (0012345등 가능)

문제 해결 전략

우선 격자의 크기가 크지 않기 때문에 모든 칸에서 bfs나 dfs를 적용한 후 생성된 숫자가 중복된 숫자가 아니면 카운트를 1씩 증가하면 된다.

중복된 숫자임을 확인하기 위해 set 자료구조를 이용하였다.

코드

#include<iostream>
#include<set>
#include<queue>
 
using namespace std;
 
int xpos[4] = {-1,1,0,0};
int ypos[4] = {0,0,1,-1};
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int arr[4][4] = {0, };
        set<int> s;
        queue<pair<int,pair<pair<int,int>,int>>>q;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                cin >> arr[i][j];
            }
        }
         
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                q.push(make_pair(arr[i][j],make_pair(make_pair(i,j),1)));
                 
                while(!q.empty())
                {
                    int x = q.front().second.first.first;
                    int y = q.front().second.first.second;
                    int l = q.front().second.second;
                    int tmp = q.front().first;
                    q.pop();
                    if(l == 7){
                        s.insert(tmp);
                        continue;
                    }
                     
                    for(int ii=0;ii<4;ii++)
                    {
                        int nx = x + xpos[ii];
                        int ny = y + ypos[ii];
                        int ntmp = tmp*10;
                        if(nx<0 || nx>=4 || ny<0 || ny>=4)
                            continue;
                        ntmp += arr[nx][ny];
                        q.push(make_pair(ntmp,make_pair(make_pair(nx,ny),l+1)));
                    }
                }
            }
        }
         
        cout << "#" << test_case << " " << s.size() << "\n";
    }
    return 0;
}

생각해볼 점
중복 여부를 확인하기 위해 set 자료구조를 사용하였는데, set은 삽입 및 검색에 있어서 O(logn)의 시간복잡도를 갖는다.

자리수가 그리 크지 않기 때문에 7자리를 모두 포함할 수 있는 크기인 10000000 만큼 배열을 할당해서 중복 여부를 확인한다면 삽입과 검색이 O(1)의 시간복잡도를 가질 수 있다.

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB