거리 동전합 최대

	static int m;
    static int n;
    static int max = Integer.MIN_VALUE;
    static int[] dX = {1, 1, 1};
    static int[] dY = {-1, 0, 1};

    public static int solution(int[][] coins) {

        m = coins.length;
        n = coins[0].length;

        dfs(coins, 0, 0, coins[0][0], true);

        return max;
    }

    private static void dfs(int[][] coins, int x, int y, int sum, boolean isFirst) {

        if (x == m-1) {
            if (isFirst) {
                dfs(coins, 0, n - 1, sum + coins[0][n-1], false);
            } else {
                max = Math.max(sum, max);
            }
        } else {
            coins[x][y] = 0;
            for (int i = 0; i < 3; i++) {
                int tmpX = x + dX[i];
                int tmpY = y + dY[i];
                if (tmpY >= 0 && tmpY < n) {
                    dfs(coins, tmpX, tmpY, sum + coins[tmpX][tmpY], isFirst);
                }
            }
        }
    }