SWEA 2805번 문제: 농작물 수확하기

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB

나의 풀이 (시간 초과)

DFS를 사용하여 재귀적으로 문제를 해결하려고 했으나 시간 초과로 인해 오답 처리가 되었다.
델타 배열을 사용한 4방 탐색과 현재 위치의 방문 여부를 저장하는 visited 2차원 배열을 사용했지만, 시간 복잡도가 높게 나오는 것 같다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * SW Expert Academy 2805번 문제: 농작물 수확하기
 */
public class FailedSolution {
    private static int[][] farm;
    private static boolean[][] visited;
    private static int revenue, n;

    // 상 -> 우 -> 하 -> 좌 (시계 방향)
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            revenue = 0;
            
            n = Integer.parseInt(br.readLine());
            farm = new int[n][n];
            visited = new boolean[n][n];
            
            // 농장 초기화
            for (int i = 0; i < n; i++) {
                String row = br.readLine();
                for (int j = 0; j < n; j++) {
                    farm[i][j] = row.charAt(j) - '0';
                }
            }
            
            visit(n/2, n/2, n/2);
            
            System.out.println("#" + tc + " " + revenue);
        }
      
        br.close();
    }
    
    public static void visit(int row, int col, int maxMoveCnt) {
        // 범위를 벗어났는가?
        if (row < 0 || row >= n || col < 0 || col >= n) return;
        
        // 현 위치를 방문하지 않았으면 이익 추가
        if (!visited[row][col]) revenue += farm[row][col];
        
        // 방문한 행, 열을 배열에 추가
        visited[row][col] = true;
        
        // 최대 이동 거리에 다다랐는가?
        if (maxMoveCnt == 0) return;
        
        // 위쪽부터 시계 방향으로 4방 탐색
        for (int i = 0; i < dr.length; i++) {
            visit(row + dr[i], col + dc[i], maxMoveCnt - 1);
        }
    }
}

풀이

첫 번째 방법

복잡하게 생각할 필요가 없었다. *로 피라미드나 마름모를 그리듯이 규칙성을 가지고 계산하면 되는 문제였다.
왼쪽에서부터 공백을 고려하면서 총 수익을 구하면 되는 문제이다. 농장의 너비가 n이라고 할 때, 첫 번째 행의 왼쪽 여백(수확할 수 없는 땅)은 소수점을 버린 n/2부터 시작하여 하나씩 감소한다. 그리고 가운데 행에서 여백이 사라지고, 이때를 기점으로 다시 여백이 하나씩 늘어난다.
수확 가능한 땅은 첫 번째 행에서 한 개부터 시작하여, 가운데 행에서 정점을 찍고, 다시 점점 줄어들어 마지막 행에서 한 개만 수확 가능하도록 되어 있다.
이를 정리하면, 현재 행의 수확 가능한 땅은 왼쪽 공백의 개수 space부터, 밭 너비 n에서 오른쪽 공백의 개수 space를 뺀 값 직전까지이다.
space는 n/2부터 시작하여 하나씩 감소하고, 가운데 행에서 다시 하나씩 증가시킨다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * SW Expert Academy 2805번 문제: 농작물 수확하기
 */
public class Solution {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int revenue = 0;
            
            int n = Integer.parseInt(br.readLine());
            int[][] farm = new int[n][n];

            // 농장 초기화
            for (int i = 0; i < n; i++) {
                String row = br.readLine();
                for (int j = 0; j < n; j++) {
                    farm[i][j] = row.charAt(j) - '0';
                }
            }
            
            // 방법 1: 왼쪽에서부터 공백을 고려하여 계산
            int space = n / 2;
            for (int i = 0; i < n; i++) {
                for (int j = space; j < n - space; j++) {
                    revenue += farm[i][j];
                }
                
                if (i < n/2) space--;
                else space++;
            }
            
            System.out.println("#" + tc + " " + revenue);
        }
        
        br.close();
    }
}

두 번째 방법

열의 중앙에서부터 양쪽으로 수확 너비를 고려하면서 계산하는 방법도 있다. 가운데부터 양 옆까지의 거리를 gap이라고 하면, 가운데 행까지 gap을 하나씩 증가시키고, 마지막 행까지 gap을 하나씩 감소시키는 방법이다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * SW Expert Academy 2805번 문제: 농작물 수확하기
 */
public class Solution {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int revenue = 0;
            
            int n = Integer.parseInt(br.readLine());
            int[][] farm = new int[n][n];

            // 농장 초기화
            for (int i = 0; i < n; i++) {
                String row = br.readLine();
                for (int j = 0; j < n; j++) {
                    farm[i][j] = row.charAt(j) - '0';
                }
            }
            
            // 방법 2: 중앙에서부터 수확 너비를 고려하여 계산
            int gap = 0;
            for (int i = 0; i < n; i++) {
                for (int j = n/2 - gap; j <= n/2 + gap; j++) {
                    revenue += farm[i][j];
                }
                
                if (i < n/2) gap++;
                else gap--;
            }
            
            System.out.println("#" + tc + " " + revenue);
        }
        
        br.close();
    }
}