백준 2210 - 숫자판 점프(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

완전탐색을 이용한 그래프 문제입니다.

5*5 숫자판에서 무작위 위치에서 5번까지 이동해 수열을 구하는 문제입니다.

 

1을 5번 이동했다면 11111이 수열이 됩니다.

만들 수 있는 수열이 숫자판에 따라 11111 ~ 99999까지 있을 수 있습니다.

따라서 이전에 만들었던 수열을 찾는 배열 칸은 100000 이상으로만 잡아주면 됩니다.

 

아무 위치에서부터 움직일 수 있으니 (0, 0) ~ (4, 4)까지 모든 곳에서 시작해줍니다. -> for문 사용

 

이전에 방문했던 곳을 다시 방문할 수 있기 때문에 방문한 위치를 저장할 필요는 없습니다.

대신에 만든 수열을 저장할 배열은 필요합니다. -> check 배열

 

수열으로서 저장하기 때문에 값을 계속 더해줘야합니다.

따라서 이전에 저장된 값에 10을 곱한 뒤, 현재 있는 숫자판의 값을 더해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
using namespace std;

int map[5][5];
int check[1000000];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ans;

void dfs(int x, int y, int sum, int cnt){
    if(cnt == 5){
        if(check[sum] == 0){
            check[sum] = 1;
            ans++;
        }
        return;
    }
    for(int i = 0; i < 4; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 0 && xx < 5 && yy >= 0 && yy < 5){
            dfs(xx, yy, sum*10+map[xx][yy], cnt + 1);
        }
    }
}

void solve(){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            dfs(i, j, map[i][j], 0);
        }
    }
    cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요