백준 1189번 : 컴백홈 (C 언어)

https://www.acmicpc.net/problem/1189

1189번: 컴백홈

Code:

#include <stdio.h>
 
char arr[6][6] = { 0, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int check[6][6] = { 0, };
int r, c, k;
int result = 0;
 
void dfs(int y, int x, int dis)
{
    if (dis == k && y == 0 && x == c - 1)
    {
        result++;
        return;
    }
    for (int k = 0; k < 4; k++)
    {
        int y_n = y + dy[k];
        int x_n = x + dx[k];
        if (arr[y_n][x_n] == 'T' || y_n < 0 || y_n >= r || x_n < 0 || x_n >= c||check[y_n][x_n]==1)
        {
            continue;
        }
        check[y_n][x_n] = 1;
        dfs(y_n, x_n, dis + 1);
        check[y_n][x_n] = 0;
    }
}
 
int main() {
    scanf("%d %d %d", &r, &c, &k);
    for (int i = 0; i < r; i++)
    {
        scanf("%s", arr[i]);
    }
    check[r - 1][0] = 1;
    dfs(r - 1, 0, 1);
    printf("%d", result);
}

문제 설명:

이 문제에서는 R x C 크기의 길이 주어지고, 그 중에서 갈 수 있는 길을 '.'로 표시하고 갈 수 없는 부분을 'T'로 표시합니다. 한수는 왼쪽 아래에서 출발하여 오른쪽 위에 있는 집에 돌아가야 하며, 한 번 지나친 곳은 다시 방문하지 않습니다. 주어진 거리 K 내에서 집까지 돌아가는 경우 중 가짓수를 구해야 합니다.문제 해결 방법 설명:

1. 입력 받기:
2. 먼저, R x C 크기의 미로와 목표 거리 K, 미로 정보를 입력으로 받습니다.
3. DFS (깊이 우선 탐색) 함수 설명:
   • dfs(int y, int x, int dis): DFS 함수는 현재 위치 (y, x)와 현재까지 이동한 거리 dis를 인자로 받습니다.
   • dis가 K와 일치하며, 집에 도달한 경우:
     • 목표 거리 K에 도달하고, 현재 위치가 집(오른쪽 위)인 경우, 결과 변수를 증가시킵니다.
   • 상하좌우 방향을 탐색하며 다음 위치를 검사:
     • y_n, x_n은 다음 위치의 좌표를 나타냅니다.
     • 다음 위치가 벽('T')이거나 미로 범위를 벗어나면 스킵합니다.
     • 다음 위치를 방문 표시하고, DFS 함수를 재귀적으로 호출합니다.
     • DFS 함수 호출이 끝나면 다음 위치의 방문 표시를 해제합니다.
4. 시작 위치 설정:
5. 시작 위치는 미로의 왼쪽 아래 (R-1, 0)입니다. 이 위치를 방문 표시하고, 거리 1로 시작하여 DFS 함수를 호출합니다.
6. DFS 함수 호출:
7. 시작 위치부터 DFS 함수를 호출하여 가능한 모든 경로를 탐색합니다. 거리가 K인 경우를 찾을 때마다 결과 변수를 증가시킵니다.
8. 결과 출력:
9. DFS 함수 호출이 끝난 후, 결과 변수에 저장된 거리가 K인 경로의 수를 출력합니다.