문제 푼 날짜 : 2021-10-01

문제

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

접근 및 풀이

DP와 DFS를 이용한 그래프 탐색문제이다.
문제에 입력으로 주어진 보드의 (0, 0)부터 시작하여 게임이 끝날 때까지 DFS로 탐색한다.
탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에서 게임이 끝날 때까지 동전을 몇 번 움직일 수 있는지이다.
이를 이용하여 탐색하면서 dp 배열을 업데이트시켜주었다.
업데이트 시켜주면서 주의해야할 점은 동전이 무한대로 움직이는 경우이다. 이는 싸이클이 생기는 경우이므로, visited 배열로 이전에 탐색했던 곳을 체크해주어 또 방문하면 -1을 return 해주었다.

코드

// 백준 1103번 : 게임
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<string> board;
int dp[51][51];
bool visited[51][51];
int D[4][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};

int dfs(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M || board[y][x] == 'H') { // 게임 종료
        return 0;
    }
    if (visited[y][x]) { // 이미 방문한 곳이라면 싸이클이 생겨 무한번 움직이므로 종료
        cout << -1;
        exit(0);
    }
    int &ret = dp[y][x];
    if (ret != -1) {
        return ret;
    }
    ret = 0;
    visited[y][x] = true;
    
    for (int i = 0; i < 4; i++) {
        int nextY = y + D[i][0] * (board[y][x] - '0');
        int nextX = x + D[i][1] * (board[y][x] - '0');

        ret = max(ret, 1 + dfs(nextY, nextX));
    }
    visited[y][x] = false;
    return ret;
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string str = "";
        cin >> str;
        board.push_back(str);
    }

    memset(dp, -1, sizeof(dp));
    memset(visited, false, sizeof(visited));
    int ans = dfs(0, 0);

    cout << ans;
    return 0;
}

결과

피드백

연습만이 살길이다.