SWEA 12712 파리퇴치3

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    static int[] lr = {1,1,-1,-1};
    static int[] lc = {1,-1,1,-1};
    static int[][] map;
    static int sum=0;
    static int max = 0;
    static int N;
    static int M;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			N = sc.nextInt();
            M = sc.nextInt();
            map = new int[N][N];
            max=0;
            for(int i =0; i<N; i++){
                for(int j = 0; j<N; j++){
                    map[i][j] = sc.nextInt();
                }
            }
            
            for(int i =0; i<N; i++){
                for(int j = 0; j<N; j++){
                    sum = map[i][j];
                    for(int k = 0; k<4; k++){
                        ddfs(i,j,k,1);// 가로,세로로 분사
                    }
                    
                    max = Math.max(sum,max);
                    sum = map[i][j];
                    for(int k = 0; k<4; k++){
                        ldfs(i,j,k,1);// 대각선으로 분사
                    }
                    max = Math.max(sum,max);
                }
            }
            System.out.println("#"+test_case+" "+max);

		}
	}
    public static void ddfs(int row, int col,int dir,int count){
        if(count==M) return;
        int nrow = row + dr[dir];
        int ncol = col + dc[dir];
        if(nrow<0||ncol<0||nrow>=N||ncol>=N) return;
        sum+=map[nrow][ncol];
        ddfs(nrow,ncol,dir,count+1);
    }
     public static void ldfs(int row, int col,int dir,int count){
         if(count==M) return;
        int nrow = row + lr[dir];
        int ncol = col + lc[dir];
        if(nrow<0||ncol<0||nrow>=N||ncol>=N) return;
        sum+=map[nrow][ncol];
        ldfs(nrow,ncol,dir,count+1);
    }
    
}

풀이방법

1. 완전탐색으로 맵전체를 탐색한다.
2. 해당 좌표에서 가로,세로로 분사하여 잡은 파리와 대각선으로 분사하여 잡은 파리를 계산하여 최댓값을 구하며 탐색한다.
3. ddfs함수에 좌표와 방향, count를 넘겨주고, 각 방향의 파리값을 한칸씩 sum에 더해준다.
4. count가 M이 되는 시점에 함수를 빠져나온다.

후기

특이하게 대각선 방향과 가로,세로 방향의 값을 더해서 최댓값을 구하게 하는 문제였다.