[SWEA] 2819번 격자판의 숫자 이어 붙이기

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

풀이)

dfs를 이용해서 서로 다른 일곱 자리 수들을 구한 문제이다.

숫자의 자릿수가 늘어날 때마다 *10씩 하는 게 귀찮아서

아예 string으로 선언해 stoi()함수로 수를 쉽게 구했다.

첫번째 풀이에서 일곱 자리 수들의 개수를 bool visited[1000000]을 통해 확인해주었고,

이는 메모리를 너무 잡아먹었다.

코드)

#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <set>
using namespace std;
 
int arr[4][4];
int check[10000000];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void dfs(int y,int x,string s){
    if (s.length() == 7) {
        if (!check[stoi(s)]) check[stoi(s)] = true;
 
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
           
            dfs(ny, nx, s + to_string(arr[ny][nx]));
           
        }
    }
}
 
int main(){
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                dfs(i, j, "");
            }
        }
        int result = 0;
        for (int i = 0; i < 10000000; i++) {
            if (check[i]) {
                result++;
                check[i] = false;
            }
        }
        printf("#%d %d\n", test_case, result);
         
    }
    return 0;
}

그래서 두번째 풀이로 set을 이용해 개수를 확인해줬다.

(메모리가 3배정도 이득이었다)

(test case 끝날 때마다 set 변수 초기화 시켜야 함을 주의)

코드)

#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <set>
using namespace std;
 
int arr[4][4];
set<string>check;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void dfs(int y,int x,string s){
    if (s.length() == 7) {
        check.insert(s);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
            dfs(ny, nx, s + to_string(arr[ny][nx]));
        }
    }
}
 
int main(){
    freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                dfs(i, j, "");
            }
        }
        
        printf("#%d %d\n", test_case, check.size());
        check.clear();
    }
    return 0;
}