SWEA-D2-12712.파리퇴치3

문제

제약사항

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

입출력 예시

아이디어

변수 및 자료 설정

• 지도 데이터
  - N*N 지도 표시하는 2차원 배열 필요
  • 이 때, 스프레이 사용 시 양 모서리에서도 계산이 동일할 수 있도록 확장 배열 사용

    int[][] map = new int[n+m+m][n+m+m]

• 델타 배열 - 상하좌우
  - dr1, dc1
• 델타 배열 - 대각선
  - dr2,dc2
• 최대 파리 수
  • int max

고려사항

• 인덱스 범위 문제
  - 스프레이를 뿌릴 때, 중앙이 아닌 가장자리에서 뿌린다면 map 범위 벗어날 수 있음.
  • 배열의 크기를 상하좌우 각각 M만큼 더 크게 여유를 둠
    • 이 때 모서리 값들은 0으로.
    • 한 변의 길이 = n+m+m
  • 조건문 등 다른 요소 없이 동일한 코드로 탐색 가능
• 스프레이 형태에 따른 파리 수 고려 필요
  - +형태 / X 형태 중 더 큰 값 찾아야 함
  • 각 좌표마다 두 형태를 모두 계산하여 더 큰 값을 업데이트

문제 접근 방법

• 지도 배열 확장
  - 상하좌우로 m만큼 확장된 지도에 내부 값을 입력받는다
  • 이 때, (0,0)부터 값 입력받지 않음.
  • 상,좌의 패딩을 제외한 m부터 입력
• 델타 탐색
  - 십자 / 대각선 각각의 델타 배열 조합을 적용

코드

전체 코드

import java.util.Scanner;
import java.io.FileInputStream;
 
 
class Solution
{
//델타
    static int[] dr1 = { -1, 1, 0, 0 };
    static int[] dc1 = { 0, 0, -1, 1 };
    static int[] dr2 = { -1, -1, 1, 1 };
    static int[] dc2 = { -1, 1, -1, 1 };
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int test = sc.nextInt();
        for (int t = 1; t <= test; t++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
 //map 초기화
            int[][] map = new int[n + m + m][n + m + m];
            for (int i = m; i < n + m; i++) {
                for (int j = m; j < n + m; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
 
            // 십자
            int max = 0;
 
            for (int r = m; r < n + m; r++) {
                for (int c = m; c < n + m; c++) {
                    int sum = map[r][c];
 
                    for (int d = 0; d < 4; d++) {
                        for (int k = 1; k < m; k++) {
 
                            int dr = r + dr1[d] * k;
                            int dc = c + dc1[d] * k;
 
                            sum += map[dr][dc];
 
                        }
                    }
                    if (sum > max)
                        max = sum;
 
                }
            }
            // 대각선
 
            for (int r = m; r < n + m; r++) {
                for (int c = m; c < n + m; c++) {
                    int sum = map[r][c];
                    for (int d = 0; d < 4; d++) {
                        for (int k = 1; k < m; k++) {
 
                            int dr = r + dr2[d] * k;
                            int dc = c + dc2[d] * k;
 
                            sum += map[dr][dc];
 
                        }
                    }
                    if (sum > max)
                        max = sum;
 
                }
            }
 
            System.out.printf("#%d %d%n", t, max);
 
        }
    }
}

코드 설명

map 초기화

//map 초기화
            int[][] map = new int[n + m + m][n + m + m];
            for (int i = m; i < n + m; i++) {
                for (int j = m; j < n + m; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

십자 델타 탐색

// 십자
            int max = 0;
 
            for (int r = m; r < n + m; r++) {
                for (int c = m; c < n + m; c++) {
                    int sum = map[r][c];
 
                    for (int d = 0; d < 4; d++) {
                        for (int k = 1; k < m; k++) {
 
                            int dr = r + dr1[d] * k;
                            int dc = c + dc1[d] * k;
 
                            sum += map[dr][dc];
 
                        }
                    }
                    if (sum > max)
                        max = sum;
 
                }
            }

대각선 델타 탐색

// 대각선
 
            for (int r = m; r < n + m; r++) {
                for (int c = m; c < n + m; c++) {
                    int sum = map[r][c];
                    for (int d = 0; d < 4; d++) {
                        for (int k = 1; k < m; k++) {
 
                            int dr = r + dr2[d] * k;
                            int dc = c + dc2[d] * k;
 
                            sum += map[dr][dc];
 
                        }
                    }
                    if (sum > max)
                        max = sum;
 
                }
            }

정리

• 배열 범위 벗어나는 조건이 문제에 있다면 map 자체를 확장하는 방식도 편하더라
• 델타 배열 활용
  - 델타 배열 쓸 때 for문 내부 범위를 잘 설정할 것.
  - int d = 0; d < 4; d++ ...