[java]파리퇴치 3 - SWEA 12712

풀이

문제 해석을 하자면,

• 2가지(+, x) 스프레이 분사 방식을 사용해서 제일 최대 파리수를 구하면?

풀이

• 범위가 크지 않아서 완전탐색으로 해결하자
• 방향 설정을한 dx, dy, dx2, dy2 가 이 문제에선 핵심인 것 같다.

코드

import java.util.*;
public class 파리퇴치3_12712 {
  public static int N, M;
  public static long result;
  public static int[] dx = {-1, 0, 1, 0};
  public static int[] dy = {0, 1, 0, -1};
  public static int[] dx2 = {-1, 1, 1, -1};
  public static int[] dy2 = {1, 1, -1, -1};

  public static void dfs(int cx, int cy, int[][] inArr) {
    long sum = inArr[cx][cy];
    // 1. '+'형 분사
    for(int i=0; i<4; i++) {
      // 1-1. 방향 선택
      int nx = cx+dx[i];
      int ny = cy+dy[i];
      // 1-2. M만큼 나아가기
      for(int j=1; j<M; j++) {
        if(nx<0||ny<0||nx>=N||ny>=N) break; // 범위체크
        sum+=inArr[nx][ny];
        nx+=dx[i]; ny+=dy[i];
      }
    }
    result = Math.max(result, sum);
    sum = inArr[cx][cy];
    // 2. 'x'형 분사
    for(int i=0; i<4; i++) {
      // 1-1. 방향 선택
      int nx = cx+dx2[i];
      int ny = cy+dy2[i];
      // 1-2. M만큼 나아가기
      for(int j=1; j<M; j++) {
        if(nx<0||ny<0||nx>=N||ny>=N) break; // 범위체크
        sum+=inArr[nx][ny];
        nx+=dx2[i]; ny+=dy2[i];
      }
    }
    result = Math.max(result, sum);
  }

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();

    for(int test_case = 1; test_case <= T; test_case++) {
      N = sc.nextInt();
      M = sc.nextInt();
      result = 0;

      int[][] inArr = new int[N][N];
      for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
          inArr[i][j] = sc.nextInt();
        }
      }

      for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
          dfs(i, j, inArr);
        }
      }
      System.out.println("#" + test_case + " " + result);
    }
  }
}

느낀점

생략