[백준] 1103 게임, C++

1103번: 게임

문제 요약

동전이 보드 위에서 움직일 수 있는 최대횟수 구하기

접근

1. 생각의 흐름 1 - BFS

보드가 이차원이고 모든 방향을 탐색하면서 최대로 움직이는 횟수를 파악해야하므로 그래프 탐색중 BFS를 사용해야할 것 같았다.
BFS는 특정 지점까지의 최소 거리를 구할 때 사용하는데 이 경우에서도 충분히 사용할수 있을 거라고 생각했다. (멈추는 지점까지의 최소 거리를 구하면 최대로 움직인 거리를 구하는 거랑 같을 거니까)

간단하게 적어보면 다음과 같다.

1. (0,0) 에서 시작한다. (queue에 시작점을 추가한다.)
   1. 현재 칸에 방문처리를 한다.
   2. 해당 칸을 확인한 뒤 숫자가 아니면 0을 반환한다.
   3. 숫자면 해당 숫자만큼 거리를 띄워서 사방탐색을 한다.
   4. 방문하지 않은 점이고 범위 안에 있으면 queue에 넣는다
2. Queue를 다 돌았으면 제일 큰 값을 반환한다.

알고리즘을 작성하다 보니 방문한 점이 싸이클인지 아닌지 어떻게 확인해야할지 고민이 되었다. 방문처리를 했다고 싸이클이라고 판단할순 없었다.

2. 생각의 흐름 2 - DFS

싸이클 처리를 위해서라도 DFS를 사용하는게 편해보였다.
재귀를 사용해서 경로 체크를 하는 방식이면 현재 확인하는 지점이 지나온 경로에 있는지 쉽게 확인 할수 있을 것 같았다.
그래서 DFS로 다시 진행했다.

1. (0,0) 에서 시작한다.
   1. 현재 칸에 방문처리를 한다.
   2. 해당 칸을 확인한 뒤 숫자가 아니면 0을 반환한다.
   3. 숫자면 해당 숫자만큼 거리를 띄워서 사방탐색을 한다.
   4. 방문하지 않은 점이고 범위 안에 있으면 재귀한다.
   5. 방문한 점이면 싸이클이므로 -1을 반환하고 프로그램을 끝낸다.
   6. 모든 지점을 방문했으면 사방탐색을 하면서 갈 수 있던 가장 큰 값에 1을 더해서 반환한다. (방문할수 있는 점이 없으면 1을 반환한다.)
   7. 빠져나가면서 방문 처리를 지운다.
2. 그래프 탐색이 끝나고 나온 값을 반환한다.

struct pos {int r;int c;};

int N, M;
string board[MAX];
int visit[MAX][MAX];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

int dfs(pos cur)
{
    if (board[cur.r][cur.c] == 'H')
        return 0;

    visit[cur.r][cur.c] = 1;
    int dist = board[cur.r][cur.c] - '0';
    int ret = 0;
    int max_ret = 0;
    for (size_t i = 0; i < 4; i++)
    {
        int nr = cur.r + dr[i] * dist;
        int nc = cur.c + dc[i] * dist;

        // check range
        if (0 > nr || nr >= N || 0 > nc || nc >= M)
            continue;

        // check visit(cycle)
        if (visit[nr][nc])
            return -1;

        ret = dfs({nr, nc});
        if (ret == -1) // if cycle
            break;

        // if not cycle, save max value
        max_ret = max(max_ret, ret);    
    }

    visit[cur.r][cur.c] = 0;

    if (ret == -1) // if cycle
        return -1;

    return max_ret + 1;
}

3. 생각의 흐름 3 - DFS + DP

위의 방식(DFS)으로만 구현하면 중복되는 구간이 많을수록 시간이 많이 걸린다.
DP를 사용해서 방문한 곳의 최대 값을 저장하는 방식으로 구현하면 시간을 줄일수 있다.

int dfs(pos cur)
{
    if (memo[cur.r][cur.c]) 
        return memo[cur.r][cur.c];

    if (board[cur.r][cur.c] == 'H')
        return 0;

    visit[cur.r][cur.c] = 1;

    int dist = board[cur.r][cur.c] - '0';
    int ret = 0;
    int max_ret = 0;

    for (size_t i = 0; i < 4; i++)
    {
        int nr = cur.r + dr[i] * dist;
        int nc = cur.c + dc[i] * dist;

        // check range
        if (0 > nr || nr >= N || 0 > nc || nc >= M)
            continue;

        // check visit(cycle)
        if (visit[nr][nc])
            return -1;

        ret = dfs({nr, nc});
        if (ret == -1) // if cycle
            break;

        // if not cycle, save max value
        max_ret = max(max_ret, ret);    
    }

    // memoization
    memo[cur.r][cur.c] = max(
        memo[cur.r][cur.c],
        max_ret + 1
    );

    visit[cur.r][cur.c] = 0;

    if (ret == -1) // if cycle
        return -1;

    return max_ret + 1;
}

전체 코드

#include <iostream>
#include <string>
#include <cstring> // memset
#include <algorithm> // max
using namespace std;

#define MAX 50

struct pos {
    int r;
    int c;
};

int N, M;
string board[MAX];
int visit[MAX][MAX];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

int memo[MAX][MAX];

void init();
int dfs(pos cur);

int main()
{
    init();
    cout << dfs({0,0}) << endl;;

    return 0;
}

void init()
{
    cin >> N >> M;
    for (size_t i = 0; i < N; i++)
        cin >> board[i];

    memset(visit, 0, sizeof(int) * N * M);
    memset(memo, 0, sizeof(int) * N * M);
}

int dfs(pos cur)
{
    if (memo[cur.r][cur.c]) 
        return memo[cur.r][cur.c];

    if (board[cur.r][cur.c] == 'H') 
        return 0;

    visit[cur.r][cur.c] = 1;

    int dist = board[cur.r][cur.c] - '0';
    int ret = 0;
    int max_ret = 0;

    for (size_t i = 0; i < 4; i++)
    {
        int nr = cur.r + dr[i] * dist;
        int nc = cur.c + dc[i] * dist;
        if (0 > nr || nr >= N || 0 > nc || nc >= M) 
            continue;
        if (visit[nr][nc]) 
            return -1;

        ret = dfs({nr, nc});
        if (ret == -1) break;
        max_ret = max(max_ret, ret);
    }

    memo[cur.r][cur.c] = max(
        memo[cur.r][cur.c],
        max_ret + 1
    );

    visit[cur.r][cur.c] = 0;

    if (ret == -1) 
        return -1;
    return memo[cur.r][cur.c];
}

새로 알게된 것

1. DFS + DP