[코딩 테스트 RUN] SWEA 수업 : 12712. 파리퇴치3

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[SW Expert Academy] 12712. 파리퇴치3

SW Expert Academy

 

이거 풀고 풍선팡을 푸는 바람에 풍선팡이 별 것 아니게 되어버렸다.

델타 이동을 사용해야 한다. 그 중에서 대각선까지 포함하는 까다로운 문제. 나의 경우는 가로합과 세로합을 따로 구분하여 추가후 maxScore를 구하는 방법을 사용했다. 핵심 로직만 가져와보자.

 

            // 하, 우, 상, 좌, 우하, 우상, 좌하, 좌상
            int[] dx = { 0, 1, 0, -1, 1, 1, -1, -1 };
            int[] dy = { 1, 0, -1, 0, 1, -1, 1, -1 };
            int maxScore = 0;
            for(int x = 0 ; x < N; x++){
                for (int y = 0; y < N; y++) {
                    int crossScore = arr[x][y];
                    for (int i = 0; i < 4; i++) {
                        for (int j = 1; j < M; j++) {
                            int nx = x + dx[i] * j;
                            int ny = y + dy[i] * j;
                            if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                                crossScore += arr[nx][ny];
                            }
                        }
                    }

                    int xScore = arr[x][y];
                    for (int i = 4; i < 8; i++) {
                        for (int j = 1; j < M; j++) {
                            int nx = x + dx[i] * j;
                            int ny = y + dy[i] * j;
                            if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                                xScore += arr[nx][ny];
                            }
                        }
                    }

                    maxScore = Math.max(maxScore, Math.max(crossScore, xScore));
                }
            }

 

dx와 dy는 델타 이동의 핵심인 이동방향에 대한 배열이다. 관련해서는 아래를 참조.

 

https://bbbbabbbababababa.tistory.com/95

[Java 풀스택 과정 강의] 3월 3일

 

이 이후로는 경계선에 닿을 때까지 이동하면 되는데, X자와 +를 별개로 하기로 했다.(왜냐하면 score를 추가해서는 안되기 때문에 별개로 관리하는 편이 max값 확인에 편하다.)

중요한 부분은 각각의 score는 for문 안에 있어야 한다는 점. 새로 갱신해야 하므로 잊지 말 것.

 

델타이동의 경계는 nx와 ny로 체크하고, 경계선 체크에 걸리지 않는다면 추가하는 방식이 된다.

 

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer nm = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(nm.nextToken());
            int M = Integer.parseInt(nm.nextToken());

            int[][] arr = new int[N][N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            // 세팅 완료

            // 하, 우, 상, 좌, 우하, 우상, 좌하, 좌상
            int[] dx = { 0, 1, 0, -1, 1, 1, -1, -1 };
            int[] dy = { 1, 0, -1, 0, 1, -1, 1, -1 };
            int maxScore = 0;
            for(int x = 0 ; x < N; x++){
                for (int y = 0; y < N; y++) {
                    int crossScore = arr[x][y];
                    for (int i = 0; i < 4; i++) {
                        for (int j = 1; j < M; j++) {
                            int nx = x + dx[i] * j;
                            int ny = y + dy[i] * j;
                            if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                                crossScore += arr[nx][ny];
                            }
                        }
                    }

                    int xScore = arr[x][y];
                    for (int i = 4; i < 8; i++) {
                        for (int j = 1; j < M; j++) {
                            int nx = x + dx[i] * j;
                            int ny = y + dy[i] * j;
                            if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                                xScore += arr[nx][ny];
                            }
                        }
                    }

                    maxScore = Math.max(maxScore, Math.max(crossScore, xScore));
                }
            }

            sb.append("#").append(test_case).append(" ").append(maxScore).append("\n");
        }

        System.out.print(sb);
    }
}