[C++] 백준 1103번: 게임

🔗 문제

1103번: 게임

1103번: 게임

 

🖍 풀이

안 올리려다가 나같은 실수한 사람이 있을까봐 풀이를 올려봅니다.. 

근데 나밖에 없을 듯 ㅎ

 

DFS에서 DP를 통한 가지치기가 필요한 문제였다.

처음에는 BFS로 풀다가 방향 경로마다 visited를 생성할 수 없다는 걸 깨닫고 DFS로 전환했다.

 

문제에서 동전이 이동한 후 적혀있는 X만큼 이동하라는 조건이 있다.

근데 나는 dir 방향 한.칸.씩. 이동해서 틀렸다 ..

 

암만 생각해봐도 왜 틀린지 모르겠어서 질문 올리기 직전에 깨달았다.

dir*map[x][y] + x로 이동해야 X만큼 이동해야한다는 것을…!!!!!!

 

 

그리고 시간 초과를 위해서 DP를 반드시 사용해야한다.

• dp[x][y] : 좌표 (x, y)까지 도달하는 최장거리

이미 방문한 곳의 dp값이 지금 이동한 거리보다 긴데 뭐하러 짧은 값으로 갱신하나요.

우리가 구하는건 최대 이동 횟수인걸요.

 

 

💾  소스

#include <iostream>

const int MAX = 50 + 1;
const int dir[4][2] = {{-1, 0},{1, 0},{0, 1}, {0, -1}};

int N, M, max = 0;
int map[MAX][MAX] = {0, };
int dp[MAX][MAX] = {0, };

bool visited[MAX][MAX] = {false, };
bool isCycle = false;

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=M)
        return false;
    return true;
}

void dfs(const int r, const int c, int depth)
{
    dp[r][c] = depth;

    max = (max > depth ? max : depth);
    
    for(int d=0; d<4; ++d)
    {
        int x = r + dir[d][0] * map[r][c];
        int y = c + dir[d][1] * map[r][c];
        
        if(!isValid(x, y) || map[x][y] == -1)
            continue;
        
        // 재방문 == 싸이클 == 무한 이동 가능
        if(visited[x][y])
        {
            isCycle = true;
            return;
        }
        
        // 가지치기 (시간 줄이기)
        if(dp[x][y] > depth)
            continue;
        
        visited[x][y] = true;
        dfs(x, y, depth+1);
        
        // 싸이클 있으면 다른거 진행할 필요도 없음
        if(isCycle)
            return;
        
        visited[x][y] = false;
    }
}

int main()
{
    
    std::cin >> N >> M;
    
    char inp;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            std::cin >>inp;
            
            if(inp == 'H')
                map[i][j] = -1;
            else
                map[i][j] = inp -'0';
        }
    }
    
    isCycle = false;
    visited[0][0] = true;
    dfs(0, 0, 1);

    std::cout << (isCycle ? -1 : max);
    
    return 0;
}