컴백홈

일단 이문제 나한테 너무너무 중요하다.

일단 BFS, DFS의 개념이 들어가지만 BFS로만은 푸는것은 아니다.

BFS는 위의 사진 처럼 탐색을 (빨간줄)로 하는데

문제는

주황선으로 가는 경우도 봐야하는 것이기 때문이다.(이점을 생각을 못함)

BFS만 고집을 하다가 풀지 못하고 DFS가 어떻게 진행되는지도 파악을 못함.

여기 for문이 핵심인데 ret += go(ny, nx)라는 실험을 끝내고 visitied[ny][nx] = 0; 으로 다시 돌려놓는다.

go는 DFS의 개념을 사용한 재귀함수라서 제일위에 if문에 걸리면 종료가되면서 자신이 왔던길을 순차적으로 다시 = 0으로 돌려놓을 것이다.

정리

k가 3이라 가정을 하자.

go는 DFS이기 때문에 처음에 이런식으로 쭉 파고들어가준다. 그다음에 go의 if문을 만나서 k와 같기 때문에 1을 반환을 하고 종료를한다.

그러면 코드는 ret += go(ny, nx); 였던 부분으로 돌아가서 ret += 연산을 하러 간다.

ret는 1이 되고

방문 해제를 해준다.( visited[ny][nx] = 0; )

그다음에

여기도 방문해제한다. 이런식으로 방문했던 부분 다시 0으로 만들어놓고 DFS를 계속 돌리는 식이다.

cpp 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define endl "\n"

int n, m, k;
int visited[10][10], arr[10][10];
int dy[4] = { 0, 1, 0, -1 }, dx[4] = {-1, 0, 1, 0};
string s;
int go(int y, int x)
{
    if (y == 0 && x == m - 1)
    {
        if (k == visited[y][x]) return 1;
        return 0;
    }

    int ret = 0;
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] || arr[ny][nx] == 'T') continue;
        visited[ny][nx] = visited[y][x] + 1;
        ret += go(ny, nx);
        visited[ny][nx] = 0;
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> s;
        for (int j = 0; j < m; ++j)
        {
            arr[i][j] = s[j];
        }
    }
    visited[n - 1][0] = 1;
    cout << go(n - 1, 0) << endl;
    return 0;
}