[C++] 백준(BOJ) - 1189 : 컴백홈

02 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 1189 : 컴백홈(링크)

알고리즘

1. 브루트포스
2. 완전탐색
3. DFS

풀이

1. 출발지에서 도착지까지 DFS를 전개
2. 문제에서 주어진대로 ‘T’를 만날 경우 진행하지 못하고, 도착지까지의 거리를 재서 주어진 k 값과 비교하여 맞으면 카운팅
3. 방문처리 해제

코드

// BOJ-1189 : 컴백홈
#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0,1,0,-1 };

int n, m, k, sy, sx, ey, ex;
char a[10][10], visited[10][10];

int go(int y, int x)
{
    if (y == ey && x == ex) // 기저사례
    {
        if (k == visited[y][x]) return 1; // 유효한 경우의 수만 더하기
        else return 0;
    }

    int res = 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] || a[ny][nx] == 'T') continue;
        visited[ny][nx] = visited[y][x] + 1;
        res += go(ny, nx);
        visited[ny][nx] = 0;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++)
        {
            a[i][j] = str[j];
        }
    }

    sy = n - 1;
    sx = 0;
    ey = 0;
    ex = m - 1;

    visited[sy][sx] = 1;

    cout << go(sy, sx) << '\n';

    return 0;
}

평가

• 매개변수로 넘기는 값의 경우에는 전역변수 사용을 주의! 지역변수로 선언하여 사용하자