[C++] SWEA 2819 - 격자판의 숫자 이어 붙이기

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

SW Expert Academy

<풀이>

1. 입력받은 4X4 배열에서 한 칸씩 시작한다.

2. 각 칸에서 갈 수 있는 4방향으로 계속 가면서 7자리의 숫자를 만든다.

3. 모든 칸에서의 탐색을 끝내고 결과를 출력한다.

​

<해법>

1. 7자리 숫자를 만드는 방법.

=> 이 문제를 처음에 만들어지는 수를 string으로 접근하였는데 시간 초과가 해결되지 않았습니다. 그래서 int로 접근하였습니다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
struct pos {
    int x, y;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int map[4][4];
bool words[10000000];
int res;
 
bool inner(int x, int y) {
    if (x < 0 || y < 0 || x >= 4 || y >= 4) {
        return false;
    }
    return true;
}
 
void go(pos cur, int word, int moveCnt) {
 
    //숫자 7개 완성 - 종료
    if (moveCnt == 7) {
        words[word] = true;
        return;
    }
 
    //기존 단어에 10을 곱해 한 자릿수 올려주고, 현재 좌표 값 더하기
    word *= 10;
    word += map[cur.x][cur.y];
 
    //4방향 중 갈 수 있는 곳으로 탐색
    for (int i = 0; i < 4; i++) {
        pos nxt = cur;
 
        nxt.x += di[i];
        nxt.y += dj[i];
 
        if (!inner(nxt.x, nxt.y)) {
            continue;
        }
 
        go(nxt, word, moveCnt + 1);
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //사용할 변수 초기화
        memset(words, false, sizeof(words));
        res = 0;
 
        //입력
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                cin >> map[i][j];
            }
        }
 
        //각 칸마다 재귀함수
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                pos str = { i,j };
                go(str, 0, 0);
            }
        }
 
        //결과 카운트 및 출력
        int res = 0;
        for (int i = 0; i < 10000000; i++) {
            if (words[i]) {
                res++;
            }
        }
        cout << "#" << test_case << " " << res << "\n";
    }
    return 0;
}

 

재귀함수에 대해 알아볼 수 있는 문제였습니다.