[C++/Softeer] Lv3. 순서대로 방문하기 (HSAT 7회 정기 코딩 인증평가 기출)

https://softeer.ai/practice/6246/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

현대 소프티어 Lv3. 순서대로 방문하기 C++ 풀이

 

문제 난이도는 적절해보이나, 조건 설명이 약간 아쉬웠던 문제.

최단거리는 아니고 방문했던 칸을 다시 지나지만 않으면 되는듯

전체 dfs 경우 중, 순차적으로 저장된 지점을 거치는 경우만을 count해서 해결했다.

---

#include<iostream>
#include <vector>
#include <queue>

using namespace std;

int grid[4][4]={0,};
int visited[4][4]={0,};
int n; int m;
vector<pair<int,int>> store;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int count=0;

bool canVisit(int x, int y){
    if(x<0 || x>=n || y<0 || y>=n) return false;
    if(grid[x][y] == 1) return false;
    if(visited[x][y]) return false;
    return true;
}

void dfs(int x, int y, int cnt){ // 시작 위치, 방문지점 수
    if(store[cnt]==make_pair(x,y)) {
        cnt++;
        if(cnt>=m){
            count ++;
            return;
        }
    }
    visited[x][y] = 1; // 이거 까먹었다..주의!!!
    for(int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(canVisit(nx, ny)){
            dfs(nx,ny,cnt);
        }
    }
    visited[x][y] = 0;
    return;
}

void findRoute(){
    pair<int,int> p = store[0];
    dfs(p.first, p.second, 1);
}

int main(int argc, char** argv)
{
    int tmp; int tmp2;
    int answer;
    cin >> n >> m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j) {
            cin >> grid[i][j];
        }
    }
    for(int i=0; i<m; ++i){
        cin >> tmp >> tmp2;
        store.push_back({tmp-1 , tmp2-1});
    }

    findRoute();
    cout << count;
   return 0;
}