SWEA 12712 파리퇴치3 (파이썬)

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXuARWAqDkQDFARa

[SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com](https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXuARWAqDkQDFARa)

 

---

1. 문제

[제약 사항]

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

[입력]

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

 

 

---

2. 풀이 및 해석

for tc in range(int(input())):
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    result = 0

    dr1 = [-1, 0, 1, 0]  # 델타 값을 준다.
    dc1 = [0, 1, 0, -1]  # 위, 우, 하, 좌 순으로

    for i in range(N):
        for j in range(N):  # 모든 값에 대해 접근할 것이기 때문에 일단 행과 열에 대해 반복문을 돌린다.
            sums = 0        # 임시의 더한 값을 저장해줄 변수를 만든다.
            sums += arr[i][j]         # 델타의 접근은 1부터 할 것이기 때문에 일단 해당 위치의 값을 더한다.
            for k in range(4):        # 델타의 접근 방향 설정
                for l in range(1, M): # 델타 접근이 어디까지 갈 것인가, 1부터 M까지 간다.
                    lr, lc = i + dr1[k] * l, j + dc1[k] * l  # 첫 델타는 현재 위치 중심으로 l번 곱해준다.
                    if lc < 0 or lc >= N or lr < 0 or lr >= N:  # 델타가 원래의 배열을 벗어나면
                        break                                   # 브레이크 걸어줌
                    sums += arr[lr][lc]  # 델타 접근 값을 더해준다.
            if sums > result:            # 최종 반환할 값인 result와의 임시 더해준 값을 비교해서
                result = sums            # 임시의 sums가 result보다 크면 result는 sums가 된다.
                sums = 0

    dr2 = [1, -1, -1, 1]   # 위 과정과 똑같다.
    dc2 = [1, 1, -1, -1]   # 다만, 델타를 4방향의 대각선으로 준 것.

    for i in range(N):
        for j in range(N):
            sums = 0
            sums += arr[i][j]
            for k in range(4):
                for l in range(1, M):
                    lr, lc = i + dr2[k]*l, j + dc2[k]*l
                    if lc < 0 or lc >= N or lr < 0 or lr >= N:
                        break
                    sums += arr[lr][lc]
            if sums > result:
                result = sums
    print(f'#{tc+1} {result}')

 

 

---

3. 후기

어떻게 보면 간단하고... 어떻게 보면 어렵고...

일단, 풀이의 접근 방식은 간단한 것 같다. 모든 위치를 탐색하는데 델타값을 줘서 그 값을 더한다.

문제는, 이를 코드로 표현하기가 쉽지는 않았다.

sums를 어디에 줘야되고, 델타설정과 그 델타가 어디까지 갈 것인지 for문의 위치를 정해주는게 어려웠다.

이 문제를 통해 델타에 대해 조금은 이해한 것 같다.