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

SWEA - ‘2819. 격자판의 숫자 이어 붙이기’ 알고리즘 문제 풀이

분류

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

풀이

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

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 커쳐도 될 때, 서로 다른 일곱 자리 수들의 개수를 출력하여라.

---

크기가 4x4로 작기 때문에 DFS 또는 BFS를 사용하여, 중복되지 않고 만들 수 있는 모든 경우의 수를 구하면 된다.

소스 코드

#include <iostream>
#include <set>
using namespace std;
 
 
const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };
 
int T;
int m[4][4];
bool visited[4][4];
set<int> s;
void dfs(int r, int c, int len, int num) {
    if (len == 7) {
        s.insert(num);
        return;
    }
    for (int d = 0; d != 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4) continue;
        dfs(nr, nc, len + 1, num * 10 + m[nr][nc]);
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                cin >> m[i][j];
            }
        }
 
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                dfs(i, j, 1, m[i][j]);
            }
        }
        cout << "#" << t << ' ' << s.size() << '\n';
        s.clear();
    }
    return 0;
}