[SWEA #16268] 풍선팡2

문제

종이 꽃가루가 들어있는 풍선이 NxM 크기의 격자판에 붙어있는데, 어떤 풍선을 터뜨리면 상하좌우의 풍선이 추가로 터진다고 한다.

다음의 경우 가운데 풍선을 터뜨리면 상하좌우의 풍선이 추가로 1개씩 터지면서 총 5개의 꽃가루가 날리게 된다.

NxM개의 풍선에 들어있는 종이 꽃가루 개수A가 주어지면, 한 개의 풍선을 선택해 터뜨렸을 때 날릴 수 있는 꽃가루 수 중 최대값을 출력하는 프로그램을 만드시오.

(3<=N, M<=100)

 

입력

첫 줄에 테스트케이스 수 T, 다음 줄부터 테스트케이스 별로 첫 줄에 N과 M, 이후 N줄에 걸쳐 M개씩 풍선에 든 종이 꽃가루 개수가 주어진다.

 

출력

#과 테스트케이스 번호, 빈칸에 이어 종이 꽃가루의 최대 개수를 출력한다.

 

내가 쓴 코드

#   우 하 좌 상
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

T = int(input())
for t in range(T):
    N, M = map(int, input().split())        # N x M 공간
    arr = [list(map(int, input().split())) for _ in range(N)]
    max_sum = 0                             # 꽃가루 수 합의 최대값

    for i in range(N):                      # 풍선 좌표 (i, j)
        for j in range(M):
            f_sum = arr[i][j]               # 꽃가루 수 합
            for k in range(4):              # 풍선의 우하좌상 좌표 (ni, nj)
                ni = i + di[k]
                nj = j + dj[k]
                if 0<=ni<N and 0<=nj<M:     # 유효값 조건
                    f_sum += arr[ni][nj]    # 우하좌상 값 더하기

            if f_sum > max_sum:             #꽃가루 수 합 최대값 구하기
                max_sum = f_sum

    print(f'#{t+1} {max_sum}')

며칠 전에 delta를 배웠다. 한 번도 문제에 적용해 본 적 없었는데, 드디어 문제에 적용해 풀어봤다!

몇 번 풀어보면 더 감이 생길지도,, ㅎㅎ

 

출력 결과