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

📝  풀이 과정

현재 방문한 위치가 node[i].first, node[i].second라면 index+1 하고 해당 노드 방문, 아니면 index 유지하고해당 노드 방문, 순서대로 방문했는지 여부는 이것으로 체크할 수 있음

(2,0) → (2,1) → (1,1) → (0,1) → (0,2) → (1,2)

(2,0) → (2,1) → (1,1) → (0,1) → (0,0) → (0,1) → (0,2) → (1,2)

(2,0) → (1,0) → (1,1) → (0,1) → (0,2) → (1,2)

(2,0) → (1,0) → (0,0) → (0,1) → (0,2) → (1,2)

(2,0) → (1,0) → (0,0) → (0,1) → (1,1) → (1,2)

계속 index 또는 index+1로 재귀 호출을 하므로, 계속 재귀호출하다가 마지막 순서를 방문하면 result++하고 리턴.

함수가 리턴을 하게 되면 마지막 실행 위치에서 다음을 실행하게 될 것.

따라서 방문을 다시 초기화해서 다음 경우의 수를 구하도록 함.

			if(cx == node[index].first && cy == node[index].second){
                search(cx, cy, index+1);
            } else{
                search(cx, cy, index);
            }

이렇게 if문으로 하면 결과가 잘 나왔는데, 삼항연산자 썼을 땐 +1 값이 구해졌음. 그래서 그냥 if문 사용함.

 

테스트케이스로 확인

 

📝 제출 코드

#include<iostream>
#include<vector>

using namespace std;
int nx[] = {0,0,1,-1};
int ny[] = {1,-1,0,0};
int n,m,result=0;
vector<pair<int,int>> node; // 방문해야 하는 위치(x,y) m개
int graph[4][4]={0,};
int check[4][4]={0,};

int search(int x, int y, int index){
    // 모든 방문해야 하는 m개 지점 순서대로 방문했으면 리턴
    if(index == m){
        result++;
        //cout << endl;
        return 0;
    } 

    for(int i=0; i<4; i++){
        int cx = x + nx[i];
        int cy = y + ny[i];
        // 유효하지 않는 위치면 패스
        if(cx < 0 || cy < 0 || cx >= n || cy >= n) continue; 
        // 방문하지 않고, 벽(1)이 아니면 (cx,cy) 방문
        if(check[cx][cy] == 0 && graph[cx][cy] == 0){
            check[cx][cy] = 1;
            //cout << "visit (" << cx << "," << cy << ") \n";
            if(cx == node[index].first && cy == node[index].second){
                search(cx, cy, index+1);
            } else{
                search(cx, cy, index);
            }
            check[cx][cy] = 0;
        }
    }
}

int main(int argc, char** argv)
{
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> graph[i][j];
        }
    }

    for(int i=0; i<m; i++){
        int x,y;

        cin >> x >> y;
    
        node.push_back(make_pair(x-1,y-1));
    }
    // 지나야 하는 노드부터 시작하므로, index는 0이 아닌 1로 줌
    check[node[0].first][node[0].second] = 1;
    //cout << "visit (" << node[0].first << "," << node[0].second << ") \n";
    search(node[0].first, node[0].second, 1);
    cout << result << endl;

    return 0;
}

 

💻 정답 결과