[SW Expert Academy] 12712.파리퇴치(D2)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=%ED%8C%8C%EB%A6%AC+%ED%87%B4%EC%B9%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

Java 풀이

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int tc=s.nextInt();
        int[] dx1={0,0,-1,1};
        int[] dy1={-1,1,0,0};
        int[] dx2={-1,1,-1,1};
        int[] dy2={1,1,-1,-1};
        for(int i=1;i<=tc;i++){
            int n=s.nextInt();
            int m=s.nextInt();
            int answer=0;
            int[][] board=new int[n][n];
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    board[j][k]=s.nextInt();
                }
            }
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    int x=j;
                    int y=k;
                    int sum=board[x][y];
                    for(int t=1;t<m;t++){
                        for(int q=0;q<4;q++){
                            int nx=x+dx1[q]*t;
                            int ny=y+dy1[q]*t;
                            if(nx<0||ny<0||nx>=n||ny>=n){
                                continue;
                            }
                            sum+=board[nx][ny];
                        }
                    }
                    if(sum>answer){
                        answer=sum;
                    }
                    
                    sum=board[x][y];
                    for(int t=1;t<m;t++){
                        for(int q=0;q<4;q++){
                            int nx=x+dx2[q]*t;
                            int ny=y+dy2[q]*t;
                            if(nx<0||ny<0||nx>=n||ny>=n){
                                continue;
                            }
                            sum+=board[nx][ny];
                        }
                    }
                    if(sum>answer){
                        answer=sum;
                    }
                }
            }
            System.out.printf("#%d %d\n",i,answer);
        }
    }
}

내 생각

• 확실히 코드 작성이 더 걸리긴 하는데 코드가 파이썬보다 보기 명확한 편인거 같다. 변수 선언 같은게 확실해서...
• 뻣어나갈 4가지 방향을 미리 배열로 저장해 두고 케이스를 돌린다. 각 케이스에서는 2차원 배열을 입력을 받는다. 이중 for문을 사용해서 각 중앙점을 완전탐색으로 전부 탐색하면서 m(뻗어나갈 길이)와 q(방향)으로 각 중심점으로 부터의 잡을 수 있는 파리수를 구한 후 최종적으로 결과값과 비교하면서 최댓값을 구한다.
• 풀이시간 : 15분

---

Python 풀이

dx1=[0,0,-1,1]
dy1=[-1,1,0,0]
dx2=[1,-1,1,-1]
dy2=[-1,-1,1,1]

for tc in range(int(input())):
    answer=0
    n,m=map(int,input().split())
    arr=[]
    for i in range(n):
        arr.append(list(map(int,input().split())))
    for i in range(n):
        for j in range(n):
            sum=arr[i][j]
            for k in range(1,m):
                for t in range(4):
                    nx=i+dx1[t]*k
                    ny=j+dy1[t]*k
                    if nx<0 or ny<0 or nx>=n or ny>=n:
                        continue
                    sum+=arr[nx][ny]
            answer=max(answer,sum)
            sum=arr[i][j]
            for k in range(1,m):
                for t in range(4):
                    nx=i+dx2[t]*k
                    ny=j+dy2[t]*k
                    if nx<0 or ny<0 or nx>=n or ny>=n:
                        continue
                    sum+=arr[nx][ny]
            answer=max(answer,sum)
    print("#"+str(tc+1)+" "+str(answer))

내 생각

• 각 영역을 전부 완전탐색하면서 하나의 칸에서 뿌려지는 두가지 경우(대각선,가로/세로)를 뿌려보면서 각 뿌려지는 영역의 파리의 수를 구하고 그 수를 비교해서 최댓값을 찾는 문제이다.
• 방향을 배열로 미리 두어 m만큼 사방으로 진행하게 해 더해가면서 구했다.
• 풀이시간 : 15분