1189번 : 컴백홈 [C++]

 

문제 링크

성공 여부(걸린 시간): 성공 (28분)

아이디어

약 3년만에 C++을 사용해보았다. 그래서 컴백홈의 의미로 컴백홈을 풀었다.
문제에서 요구하는 것은 한수가 왼쪽 제일 아래(R-1, 0)에서 출발해서 오른쪽 제일 위(0, C-1)까지
K의 거리(갔던 곳을 다시 방문은 ❌)만에 도착한 경우의 수를 모두 구하게 된다.

간단한 DFS로 풀 수 있었는데
왜냐면 조건이 R과 C가 모두 5 이하이기 때문이다.

그래서 DFS를 진행하고 금번의 방문에서 도착지에 도착하면
answer++를 해주고 return
만약 그게 아니고 이미 깊이가 K를 넘어섰다면 어차피 의미 없으니 return
마지막에 answer 값 출력

그러나 오랜만에 C++로 하다보니 오류가 2번이나 떴는데 짚고 넘어가보겠다.

1. 함수 선언부가 main 뒤에 있어서 참조오류
2. 2차원 배열 동적할당 어떻게 하더라? 까먹음

함수 선언부가 main 뒤에 있어서 참조오류
알다시피 C나 C++은 함수의 선언부가 사용되는 위치보다 앞에 위치해야 한다.
이점을 잊고 있었기 때문에 static을 안해서 그랬나? java마인드로 접근하다보니 시간이 지체됨

2차원 배열 동적할당 어떻게 하더라? 까먹음
여러 방법이 존재한다. 2중 포인터로 하는 방법도 있고 벡터로 손쉽게 할 수 있는 방법이 있었는데
난 벡터를 이용해서 해주기로 했다.

-선언-
static vector<vector<int>> map;
static vector<vector<bool>> visited;

-초기화 및 동적할당-
map.assign(R, vector<int>(C, 0));
visited.assign(R, vector<bool>(C, false));

까먹지 말자

풀이 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

static int answer, R, C, K;
static int dx[] = { 1, 0, -1, 0 };
static int dy[] = { 0, -1, 0, 1 };
static vector<vector<int>> map;
static vector<vector<bool>> visited;

static void DFS(int x, int y, int depth);
static bool canGo(int x, int y);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    answer = 0; 
    cin >> R >> C >> K;
    map.assign(R, vector<int>(C, 0));
    visited.assign(R, vector<bool>(C, false));
    for (int i = 0; i < R; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < C; j++) {
            map[i][j] = input.at(j) == 'T' ? 1 : 0;
        }
    }
    visited[R - 1][0] = true;
    DFS(R-1, 0 , 1);
    cout << answer;
    return 0;
}

static bool canGo(int x, int y) {
    return x >= 0 && y >= 0 && x < R && y < C;
}
static void DFS(int x, int y, int depth) {
    if (depth > K) {
        return;
    }
    else if (depth==K && x==0 && y==C-1) {
        answer++;
        return;
    }
    for (int dir = 0; dir < 4; dir++) {
        int mx = x + dx[dir];
        int my = y + dy[dir];
        if (canGo(mx, my) && !visited[mx][my] && map[mx][my]==0) {
            visited[mx][my] = true;
            DFS(mx, my, depth + 1);
            visited[mx][my] = false;
        }
    }
}