(SWEA c++)2819. 격자판의 숫자 이어 붙이기

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1 

SW Expert Academy

set과 BFS를 통한 완전 탐색.

 

우선 4 x 4 크기의 보드를 입력 받는다.

 

이후 이 보드를 돌면서 BFS 탐색을 진행하면 된다.

이중 for문을 탐색하면서 현재 좌표의 숫자와 x좌표, y좌표를 큐에 넣으면서 BFS를 시작.

숫자는 7자리를 만들어야 하기 때문에 move = 7로 시작한다.

 

move가 0이 될 때까지 while문 반복.

이 while문 안에서 BFS를 진행한다.

현재 큐의 크기만큼 while문을 반복해야 현재 move 자리만큼 탐색을 진행하는 것이 된다.

 

q.front().first = 현재 move 자리의 숫자

q.front().second.first = 현재 x 좌표

q.front().second.second = 현재 y 좌표

를 뜻한다.

 

directX, directY 배열을 이용해 상하좌우 좌표를 탐색하게 한다.

4 방향이기 때문에 for문도 0 ~ 4까지 반복하면서 큐에서 꺼낸 현재 x, y 좌표에서 상하좌우 방향을 탐색한다.

단, 보드의 범위를 벗어나지 않는 선에서 자리수를 늘려야 한다.

이전에 방문했던 곳도 다시 방문 가능하기 때문에 범위만 벗어나지 않도록 if 처리를 하면 된다.

 

모든 방향을 탐색하게 되면 tmpNumber는 7 - move 자리의 수가 나오게 된다.

만약 move == 0 이라면 7자리를 채웠다는 뜻이기 때문에 set에 넣어준다.

 

set은 중복되는 숫자가 들어오면 저장하지 않기 때문에 겹치지 않는 7자리의 숫자를 저장할 수 있게 된다.

마지막에는 이 set에 담겨있는 size 만큼 출력하면 된다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

int main(void) {
    int T;
    int directX[4] = {-1, 1, 0, 0};
    int directY[4] = {0, 0, -1, 1};

    cin >> T;

    for (int t = 1; t <= T; t++) {
        vector<vector<string>> board(4, vector<string>(4));
        set<string> numbers;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                cin >> board[i][j];
            }
        }
        
       for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                queue<pair<string, pair<int, int>>> q;
                int move = 7;
                
                q.push({board[i][j], {i, j}});

                while (move--) {
                    int size = q.size();

                    while (size--) {
                        string currentNumber = q.front().first;
                        int x = q.front().second.first;
                        int y = q.front().second.second;

                        q.pop();

                        for (int k = 0; k < 4; k++) {
                            string tmpNumber = currentNumber;
                            int nx = x + directX[k];
                            int ny = y + directY[k];

                            if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
                                q.push({tmpNumber + board[nx][ny], {nx, ny}});
                            }

                            if (!move) {
                                numbers.insert(tmpNumber);
                            }
                        }
                    }
                }
            }
        }
        
        cout << "#" << t << " " << numbers.size() << endl;
    }
}