[C/C++] BOJ 1103 :: 게임

BOJ 1103 :: 게임

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

DFS + DP 방식으로 문제를 풀었다!

나는 두 가지 처리를 못해서 혼자 힘으로 풀지 못했다..

1) dp 배열 안에 저장된 값이 있을 때 그것을 이용하기.

값이 있으면 바로 그 값을 return 해 주면 되는데 이 부분을 고려하지 않았다.

2) count하는 부분.

난 dfs의 인자로 count를 주어서 풀이하려고 했는데 계속 틀렸습니다. 가 떴다.

결과적으로 인자를 제외하고 코드를 변형시켰더니 맞았는데 이 부분은 내가 자세하게 파고들어서 왜 틀렸는지 알아내야 한다.. 아직 잘 모르겠다.

원래는 이 부분이

    // 범위를 넘어갈 때

    if (x < 0 || x >= N || y < 0 || y >= M)

        return 0;

    // 구멍에 빠질 때

    if (board[x][y] == 'H')

        return 0;

...

        int val = dfs(mx, my)+1;

이와 같았다.

    // 범위를 넘어갈 때

    if (x < 0 || x >= N || y < 0 || y >= M)

        return count;

    // 구멍에 빠질 때

    if (board[x][y] == 'H')

        return count;

...

        int val = dfs(mx, my, count+1);

dp로 했을 때의 장점을 살리지 못하고 무작정 코드를 짜서 내가 처리하지 못한 조건을 찾지 못한 것 같다 ㅠㅠ

짜면서도 이게 왜 더 효율적인가.. 알쏭달쏭 하더니..ㅠㅠ dp에 저장된 값을 이용하지 않았기 때문에 짜면서도 이상한 것이었다.. @@@@

생각을 하고 코딩하자!!!!!!!ㅎ.ㅎ

***

너무 힘들어서...

내일 설명 추가하겠음!!!!

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1103/BOJ_1103.cpp

// 백준알고리즘 1103번 :: 게임
 
// 접근은 맞았으나 계속 틀림.
// 틀린 원인 : dp에 값이 있을 때, 바로 return 해주지 않았다. => 시간초과
//                return count; dfs(x, y, count+1); 로 풀었는데 틀렸습니다가 나왔다
//                다른 사람의 코드를 참고하여 return 0; dfs(x,y)+1; 로 바꾸었는데 원인을 아직 정확히 파악하지 못했다.
 
// *** 래퍼런스 변수 사용 익히기
 
#include<iostream>
#include<string>
#include<memory.h>
#define max(a,b) a > b ? a: b
using namespace std;
 
int N, M;
int cycle = 0;
char board[50][50];
int dp[50][50] = {-1,};
int visited[50][50];
 
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
int dfs(int x,int y)
{
    // 범위를 넘어갈 때
    if (x < 0 || x >= N || y < 0 || y >= M)
        return 0;
    // 구멍에 빠질 때
    if (board[x][y] == 'H')
        return 0;
    // 방문한 곳을 다시 방문할 때
    if (visited[x][y]) {
        cout <<  "-1";
        exit(0);
    }
    int &ret = dp[x][y];
    if (ret != -1) return ret;
    visited[x][y] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int mx = x + (board[x][y] - '0')*dx[i];
        int my = y + (board[x][y] - '0')*dy[i];
 
        int val = dfs(mx, my)+1;
        ret = max(ret, val);
    }
    visited[x][y] = 0;
    return ret;
}
 
int main()
{
    string str;
    cin >> N >> M;
    memset(dp, -1, sizeof(dp));
 
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        for (int j = 0; j < M; j++)
        {
            board[i][j] = str[j];
        }
    }
 
    cout << dfs(0,0);
    return 0;
}