SWEA_12712_파리퇴치3, SWEA_9489_고대유적

SWEA_12712_파리퇴치3

 

문제

 

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개체 수를 의미한다.

아래는 N=5 의 예이다.

파리 킬러 스프레이를 한 번만 뿌려 최대한 많은 파리를 잡으려고 한다. 스프레이의 노즐이 + 형태로 되어있어, 스프레이는 + 혹은 x 형태로 분사된다. 스프레이를 M의 세기로 분사하면 노즐의 중심이 향한 칸부터 각 방향으로 M칸의 파리를 잡을 수 있다.
다음은 M=3 세기로 스프레이르 분사한 경우 파리가 퇴치되는 칸의 예로, +또는 x 중 하나로 분사된다. 뿌려진 일부가 영역을 벗어나도 상관없다.

한 번에 잡을 수 있는 최대 파리수를 출력하라.

제약사항 

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

입력

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

 

해결방법

- 노즐의 중심을 하나씩 옮겨가면서 십자, x 모양대로 각 원소의 합을 구해 비교하는 방식

- 델타 사용

 

코드

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())

    board = [list(map(int, input().split())) for _ in range(N)]
    
    # 4번째까지는 십자모양 이후에는 X 모양!
    d = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
    maxV = 0

    for i in range(N):
        for j in range(N):
            # 십자모양
            # 바로 방향을 줄거라서 합의 초기값은 노즐의 중심이 되는 원소의 파리!
            sumV = board[i][j]
            for di, dj in d[:4]:
                k = 1
                while k < M:
                    if 0 <= i+di*k < N and 0 <= j+dj*k < N:
                        sumV += board[i+di*k][j+dj*k]
                    k += 1

            if sumV > maxV:
                maxV = sumV

            # 엑스 모양
            sumV = board[i][j]
            for di, dj in d[4:]:
                k = 1
                while k < M:
                    if 0 <= i+di*k < N and 0 <= j+dj*k < N:
                        sumV += board[i+di*k][j+dj*k]
                    k += 1

            if sumV > maxV:
                maxV = sumV

    print(f'#{test_case} {maxV}')

 

 

 

SWEA_9489_고대유적

 

문제

 

땅속의 구조물을 촬영할 수 있는 특수 위성 카메라에 땅속에 묻힌 고대 구조물이 발견되었다. 구조물은 폭 1m, 길이 2m 이상의 직선 형태로 서로 평행 또는 직각으로만 자리하고 있으며, 1mx1m의 해상도의 사진데이터에 구조물이 있는 자리는 1로 나타난다.

0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0
0	1	1	1	1	0	1	0
0	0	0	0	0	0	1	0
0	0	0	1	0	0	1	0
0	0	0	1	0	0	1	0
0	1	1	0	0	0	1	0
0	0	0	0	0	0	0	0

 

사진의 해상도는 NxM이며, 구조물이 있는 곳은 1, 빈 땅은 0으로 표시된다. 위 그림의 경우 가장 긴 구조물은 노란색으로 표시된 영역이며, 길이는 6이다. 교차하거나 만나는 것처럼 보이는 구조물은 서로 다른 깊이에 묻힌 것이므로 직선인 구조물만 고려하면 된다.

다음과 같은 경우는 길이가 3인 구조물 4개가 겹쳐 보이는 것이다.

	1
1	1	1
	1			1
				1
		1	1	1

 

평행한 모든 구조물은 서로 1m이상 떨어져 있고, 구조물의 최소 크기는 1x2m이다.

여러 구역의 사진 데이터가 주어질 때, 각 구역 별로 가장 긴 구조물의 길이를 찾는 프로그램을 만드시오.

 

입력

 

첫 줄에 사진 데이터의 개수, 다음 줄부터 사진 데이터 별로 첫 줄에 N과 M, 이후 N개의 줄에 M개씩의 데이터가 제공된다.

(3<=N, M<=100)

 

출력

 

#과 1번부터 시작하는 사진 번호, 빈칸과 가장 긴 구조물의 길이를 출력한다.

 

해결방법

- 가로, 세로 각각 한줄 씩 검사하면서 연속된 1의 개수를 세어 최댓값 갱신

- 한 줄에 구조물이 한개 이상 존재할 수 있기 때문에 벽에 닿을때까지 검사해야 한다

while j < M:

 

코드

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())

    board = [list(map(int, input().split())) for _ in range(N)]

    maxV = 0
    # 가로방향
    for i in range(N):
        j = 0
        cnt = 0
        while j < M:
            if board[i][j] == 1:
                cnt += 1
                if cnt > maxV:
                    maxV = cnt
            else:
                cnt = 0
            j += 1

    for j in range(M):
        i = 0
        cnt = 0
        while i < N:
            if board[i][j] == 1:
                cnt += 1
                if cnt > maxV:
                    maxV = cnt
            else:
                cnt = 0
            i += 1

    print(f'#{test_case} {maxV}')

 

숙소로 돌아가는 길에 차를 돌려 지는 해를 따라갔었던!

계획된 일정은 아니었지만 가장 기억에 남는다. 1주뒤면 이 바다를 다시 볼 수 있다. 그때까지 버텨~

 

+ 연습문제로 이차원 배열을 정말 많이 줬길래 시험 직전 까지 연습했더니,,이게 무슨,,,하아아나도 안나왔당 ㅎ

그래도 패스했으니까 오늘 아아무생각도 안해야지 : )