백준 1103 게임 - C++

1103 : www.acmicpc.net/problem/1103

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 51

using namespace std;

int n, m;
string s;
int arr[MAX][MAX];
int ans[MAX][MAX];
bool visit[MAX][MAX];

int goX[4] = { 0, 0, 1, -1 };
int goY[4] = { 1, -1, 0, 0 };

int search(int x, int y){
    // 범위를 벗어나거나 구멍이면 실패
    if(x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == -1)
        return 0;
    // 사이클일 경우 무한대, -1, exit로 프로레스 종료
    if(visit[x][y]){
        printf("-1\n");
        exit(0);
    }   
    
    if(ans[x][y] != -1)
        return ans[x][y];
    
    visit[x][y] = true;
    ans[x][y] = 0;
    for(int i = 0; i < 4; i++){
        int nextX = x + (arr[x][y] * goX[i]);
        int nextY = y + (arr[x][y] * goY[i]);
        // for문의 4방향중 제일 오래할 수 있는 값을 선택
        ans[x][y] = max(ans[x][y], search(nextX, nextY) + 1);
    }
    visit[x][y] = false;

    return ans[x][y];
}

int main(){
    // 입력
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'H')
                arr[i][j] = -1;
            else
                arr[i][j] = s[j] - '0';
        }
    }
    // 계산
    memset(ans, -1, sizeof(ans));
    printf("%d\n", search(0, 0));
}

---

 문제의 조건을 봤을때 몇가지 고려해야 할 것은

    1. H 입력값은 어떻게 처리할 것인가

    2. 무한대로 간다는건 어떻게 알아낼 것인가

    3. DP 를 어떻게 구성할 것인가

 라고 생각을 했습니다. 1번의 경우 string으로 받은 뒤 처리하면 되는 간단한 것이고 무한대로 갈 수 있다는건 사이클이 발생하는 것이기 때문에

// 사이클일 경우 무한대, -1, exit로 프로레스 종료
if(visit[x][y]){
    printf("-1\n");
    exit(0);
}   

위 코드를 사용해서 처리를 했습니다. 처음에는 return -1을 하면 된다고 안일하게 생각했는데 이 프로세스를 종료해야 하는거라 exit(0)으로 처리했습니다.

int search(int x, int y){
    // 범위를 벗어나거나 구멍이면 실패
    if(x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == -1)
        return 0;
    // 사이클일 경우 무한대, -1, exit로 프로레스 종료
    if(visit[x][y]){
        printf("-1\n");
        exit(0);
    }   
    
    if(ans[x][y] != -1)
        return ans[x][y];
    
    visit[x][y] = true;
    ans[x][y] = 0;
    for(int i = 0; i < 4; i++){
        int nextX = x + (arr[x][y] * goX[i]);
        int nextY = y + (arr[x][y] * goY[i]);
        // for문의 4방향중 제일 오래할 수 있는 값을 선택
        ans[x][y] = max(ans[x][y], search(nextX, nextY) + 1);
    }
    visit[x][y] = false;

    return ans[x][y];
}

 답을 뽑아내는 핵심인 search함수의 경우 다른 문제들에 비해 조건이 많습니다. 처음으로 범위를 벗어나는 경우 0을 리턴해 아래 max에서 선택될 수 없게 처리를 했습니다. 또한 위에 말한대로 exit을 사용해 사이클은 -1 출력후 프로세스를 종료하게 했습니다.

 함수에 들어오기 전 ans 배열은 -1로 초기화를 했으며 -1이 아니라면 방문한적이 있으니 스스로를 리턴하면 됩니다.

 

 이후 좌표에 해당하는 값에 따라 4방향으로 움직이게 했으며 여기서 제일 멀리갈 수 있는 값을 max로 판별해 ans[x][y]를 수정해 줬습니다.