[C++] 백준 1189번: 컴백홈

문제

난이도 : 실버 1
백준 1189번 : 컴백홈

코드

#include <bits/stdc++.h>

using namespace std;

int R, C, K;
char arr[10][10];
int visited[10][10];

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

int answer;

void Go(int y, int x, int distance)
{
    if (y == 0 && x == C - 1)
    {
        if (distance == K) answer++;

        return;
    }

    visited[y][x] = 1;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx] || arr[ny][nx] == 'T') continue;

        Go(ny, nx, distance + 1);
    }

    visited[y][x] = 0;
}


int main()
{
    cin >> R >> C >> K;

    for (int i = 0; i < R; i++)
    {
        string input;
        cin >> input;

        for (int j = 0; j < C; j++)
        {
            arr[i][j] = input[j];
        }
    }

    Go(R - 1, 0, 1);

    cout << answer;

    return 0;
}

설명

R, C가 5이하라 완전 탐색이 가능할정도의 문제이다.
완전 탐색문제들을 풀면서 재귀 함수를 잘 이해하고 사용해야 하는데 아직 어려운 것 같다.
한수의 위치에서부터 Go 함수를 실행해 현재 위치를 방문했다고 표시하고 이동하는 로직을 구성해 다음 위치, 거리 + 1로 재귀 함수를 돌린다. 만약 집에 도착하면 return을 하는데 distance가 K라면 answer을 1씩 더해준다. 모든 로직이 끝나면 현재 위치를 방문했다는 표시를 원래되로 돌린다.

결과