백준 1103 [C++]

https://www.acmicpc.net/problem/1103

1103번: 게임

 

 

1. 풀이방법

- 처음에는 단순 dfs로 접근하긴 했지만 (오랜만에 풀이라 일단 접근했음)

 

- 하면서도 분명 제대로 구현되도 시간초과가 뜨거나 스택오버플로우가 날 것 이라 생각했습니다.

 

- 처음시도는 역시나 시간초과

 

- 시간초과라면 dp테이블을 이용해보자는 생각 !

 

- 아, 근데 오랜만에 푸니까 dp적 머리가 잘 돌아가지 않아서 고생을 좀 했습니다....

 

- 우선 테이블을 모두 -1 처리를 하고 visit이 이미 true인 곳에 다시 오면 그건 싸이클이므로

 

- -1을 출력 (무한정 왔다리갔다리 가능)

 

- dp가 -1이 아닐경우 기존에 저장되어 있는 수와 현재의 루트에서 +1 (한번 더 이동) 해서 더 많은 이동횟수로 업데이트

 

- dfs +dp 라고 할 수 있겠네요. dfs는 간단한 수준이라 생략하겠습니다.

 

 

 

2. 주의사항

 

- 시간초과

 

 

 

3. 코드

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
using namespace std;

int N, M;
int ground[50][50];
int dp[50][50];
bool visited[50][50];

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


void Input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        string inputs;
        cin >> inputs;
        for (int j = 0; j < inputs.length(); j++){
            if (inputs[j] == 'H') ground[i][j] = 0;
            else ground[i][j] = inputs[j] - '0';
        }
    }
}

int DFS(int x, int y){
    if (x < 0 || y < 0 || x >= N || y >= M || ground[x][y] == 0) return 0;
    if (visited[x][y] == true) // 무한반복이 가능
    {
        cout << -1 << endl;
        exit(0);
    }
    if (dp[x][y] != -1) return dp[x][y]; // 바로 dp 테이블에서 리턴

    visited[x][y] = true;
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++){
        int tx = x + (ground[x][y] * dx[i]);
        int ty = y + (ground[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(tx, ty) + 1);
    }
    visited[x][y] = false;
    return dp[x][y];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Input();
    memset(dp, -1, sizeof(dp)); //dp 테이블 초기화
    cout << DFS(0, 0) << endl;
    return 0;
}