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

🔗 문제

1189번: 컴백홈

1189번: 컴백홈

 

🖍 풀이

 

한수는 캠프를 마치고 집에 돌아가려 한다.

한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

 

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

 

1. 문제를 읽고 필요한 조건을 정리해 준다.
   • 출발지: (R-1, 0)
   • 목적지: (0, C-1)
   • 한수는 상하좌우로 이동할 수 있다.
   • 한 지점에 재방문할 수 없다.
   • 출발지도 K==1 이다 .
2. 코드로 표현하기 위한 조건을 정리한다.
   • 이동 거리가 K이고 현재 위치가 (0, C-1) 이면 answer를 1 증가한다.
   • if(distance == K) { if(r == 0 && c == C-1) ++answer; }
   • 재방문 조건을 방지하여 현재 위치가 x, y일 때 visited[x][y]로 방문 체크를 해야겠다.
     • 상하좌우를 이동하되 (R, C) 범위를 초과해선 안된다.
     • T 위치는 이동할 수 없다.
     • 재방문할 수 없다.

       for(int i=0; i<4; ++i)
       {
           int x =  r + dx[i];
           int y =  c + dy[i];
           
           if(!isValid(x, y) || map[x][y] == 'T' || visited[x][y])
               continue;
           
           //....
       }

 

이 후부터는 부분수열의 합을 푼 기억이 있어서 자연스럽게 재귀함수가 떠올랐다.

조건이 모두 통과하면 재귀함수를 부르고 다시 되돌아왔을 때 진행한 부분의 재방문 여부를 false로 바꾸고 다른 방향으로 진행하게 만들면 모든 경우의 수로 진행시킬 수 있다.

 

💾  소스

#include <iostream>

int R, C, K;
char map[6][6];
bool visited[6][6] = {false, };
int answer = 0;

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

bool isValid(int r, int c)
{
    if(r<0 || c<0 || r>=R || c>=C)
        return false;
    
    return true;
}

void solve(int r, int c, int distance)
{
    visited[r][c] = true;

    if(distance == K)
    {
        if(r==0 && c==C-1)
        {
            ++answer;
        }
        return;
    }

    for(int i=0; i<4; ++i)
    {
        int x =  r + dx[i];
        int y =  c + dy[i];
        
        if(!isValid(x, y) || map[x][y] == 'T' || visited[x][y])
            continue;
        
        visited[x][y] = true;
        solve(x, y, distance+1);
        visited[x][y] = false;
    }
}

int main()
{
    std::cin >> R >> C >> K;
    for(int i=0; i<R; ++i)
    {
        for(int j=0; j<C; ++j)
            std::cin >> map[i][j];
    }
    
    solve(R-1, 0, 1);
    
    std::cout << answer;
    return 0;
}