백준 1189번 [컴백홈](C++) -yes6686- 티스토리

백준 문제 풀이: 1189번 [컴백홈]

---

문제 링크: https://www.acmicpc.net/problem/1189

문제 설명:

행렬로 주어진 지도에서 한 점에서 시작하여 목표 지점까지 정확히 K번 이동하여 도달하는 모든 가능한 경로의 개수를 구하는 문제입니다. 이동은 상, 하, 좌, 우로 가능하며 장애물이 있는 경우 이동할 수 없습니다. 출발점은 (R-1, 0), 도착점은 (0, C-1)입니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

// 방향 배열: 상, 하, 좌, 우
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

// 격자 및 방문 여부 배열
int arr[5][5];
int visited[5][5];

int r, c, k; // 행, 열, 이동 횟수
int ans = 0; // 가능한 경로 수

// DFS로 경로 탐색
void dfs(int x, int y, int d) {
    if (d > k) return; // 이동 횟수가 K를 초과하면 종료
    if (d == k && x == 0 && y == c - 1) { // 조건 만족 시 경로 카운트
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 이동 시도
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 유효한 이동인지 확인
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue; // 범위 체크
        if (arr[nx][ny] == -1) continue; // 장애물 체크
        if (visited[nx][ny] == 1) continue; // 이미 방문 체크
        visited[nx][ny] = 1; // 방문 표시
        dfs(nx, ny, d + 1); // 다음 위치로 이동
        visited[nx][ny] = 0; // 방문 해제
    }
}

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL);               // 입출력 비동기화 해제

    cin >> r >> c >> k; // 격자의 크기와 이동 횟수 입력
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s; // 격자 입력
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '.') {
                arr[i][j] = 0; // 이동 가능한 칸
            } else {
                arr[i][j] = -1; // 장애물
            }
        }
    }

    visited[r - 1][0] = 1; // 시작점 방문 표시
    dfs(r - 1, 0, 1);      // DFS 탐색 시작
    cout << ans;           // 가능한 경로 수 출력
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 깊이 우선 탐색(DFS)를 사용하여 모든 가능한 경로를 탐색하며, 정확히 K번 이동한 경우에만 결과를 카운팅합니다.
• 구현 세부사항:
  • DFS는 현재 위치와 이동 횟수를 기반으로 재귀적으로 호출됩니다.
  • 방문 여부를 기록하여 이미 방문한 경로를 재방문하지 않도록 합니다.
  • 범위를 벗어나거나 장애물인 경우 이동을 중단합니다.
• 시간 복잡도 분석: 최대 O(4^K)의 시간 복잡도를 가집니다. 그러나 일반적으로 장애물과 범위 조건으로 인해 탐색 범위는 제한됩니다.

---

결과

모든 가능한 경로를 탐색하여 정확히 K번 이동하는 경로의 개수를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!