BOJ 2210 : 숫자판 점프 - C++

김정욱·2021년 4월 22일
0

Algorithm - 문제

목록 보기
236/249
post-custom-banner

숫자판 점프

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
// 0303 ~ 0321
int ans=0;
int board[6][6];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
map<string,bool> m;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin >> board[i][j];
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            queue<pair<pair<int,int>,string>> q;
            q.push({{i,j},to_string(board[i][j])});
            int cycle = 5;
            while(cycle--)
            {
                int len = q.size();
                while(len--)
                {
                    auto cur = q.front(); q.pop();
                    for(int dir=0;dir<4;dir++)
                    {
                        int ny = cur.first.first + dy[dir];
                        int nx = cur.first.second + dx[dir];
                        if(nx<0 or ny<0 or nx>=5 or ny>=5) continue;
                        string tmp = to_string(board[ny][nx]);
                        q.push({{ny,nx}, cur.second+tmp});
                    }
                }
            }
            while(!q.empty())
            {
                string s = q.front().second; q.pop();
                if(!m[s]){
                    m[s] = true;
                    ans++;
                }
            }
        }
    }
    cout << ans;
    return 0;
}
  • 문제 해결
    • 본인은 BFS를 통해 원하는 depth(5)까지만 실행해서 map을 통해 개수를 Count!
    • DFS원하는 depth까지만 수행 후 체크해도 해결 가능한 문제
profile
Developer & PhotoGrapher
post-custom-banner

0개의 댓글