(매일 BOJ) C++ 1189번 컴백홈

이번 문제는 1189번 컴백홈이다

문제 요약

• 지도는 R × C 크기의 격자
• 각 칸은 빈 칸(.) 또는 장애물(T)
• 시작점: 왼쪽 아래 (R-1, 0)
• 도착점: 오른쪽 위 (0, C-1)
• 이동은 상하좌우로만 가능
• 같은 칸을 두 번 방문할 수 없음
• 정확히 K 칸을 지나 도착해야 함

접근법

1. DFS (깊이 우선 탐색)
   • 현재 위치에서 상하좌우 탐색
   • 장애물이거나 방문한 적 있는 칸은 무시
   • 이동 거리를 하나씩 늘려가며 탐색
   • 거리가 K가 되었을 때 도착점에 있다면 경우의 수 +1
2. 백트래킹 (방문 표시 후 해제)
   • 방문 여부를 체크하면서 DFS 실행
   • 탐색 후에는 방문 해제(visited[nx][ny] = false)해서 다른 경로도 탐색 가능하게 함
3. 좌표계 처리 주의
   • 입력은 R행 × C열
   • 본 코드는 graph[C][R] 구조 (열, 행 순서)로 관리

작성코드

#include <bits/stdc++.h>
using namespace std;

int fourway_x[4] = {1,-1,0,0};
int fourway_y[4] = {0,0,1,-1};
int R,C,K;
void DFS(int & result, int x, int y,vector<vector<bool>>& visited, int dist,vector<vector<char>> & graph);

int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> R >> C >> K;
    vector<vector<char>> graph(C,vector<char>(R));

    for(int i = 0; i < R; i++){
        string str;
        cin >> str;
        for(int j = 0; j < str.size(); j++){
            graph[j][i] = str[j];
        }
    }
    vector<vector<bool>> visited(C,vector<bool>(R,false));
    visited[0][R-1] = true;
    int result = 0;
    DFS(result,0,R-1,visited,1,graph);
    cout << result;
}

void DFS(int & result, int x, int y,vector<vector<bool>>& visited, int dist,vector<vector<char>> & graph){
    if(dist == K && x == C-1 && y == 0 ){
        result += 1;
        return;
    }
    
    for(int i = 0; i < 4; i++){
        int next_x = x + fourway_x[i];
        int next_y = y + fourway_y[i];

        if(next_x < 0 || next_y < 0 || next_x >= C || next_y >= R) continue;
        if(graph[next_x][next_y] == 'T' || visited[next_x][next_y]) continue;
        visited[next_x][next_y] = true;
        DFS(result,next_x, next_y,visited,dist+1,graph);
        visited[next_x][next_y] = false;
    }   
}