[백준] 17779번 게리맨더링 2 _ 문제 풀이

 


1. 문제

https://www.acmicpc.net/problem/17779

2. 풀이

삼성 SW 역량테스트 문제입니다. 풀이 순서는 아래와 같습니다.

  1. x, y, d1, d2 의 가능한 모든 수에 대하여 for문으로 동작시켰습니다. out of index 여부로 불가능 한 경우에는 건너뜁니다.
  2. 각 구역에서 공통되는 부분을 찾아보았습니다. 아래와 같이 직사각형으로 이루어진 부분과 감소하는 부분으로 이루어져있습니다. 해당 부분의 index를 체크하여 문제를 해결해줍니다.

image

참고사항은 아래와 같습니다.

  • 중간에 복붙을 하다가 다른 값을 써버린 케이스가 있는데, 항상 헷갈리지 않게 변수를 자주 사용하는 것이 좋을 것 같습니다.
  • 다른 사람의 경우 경계선과 다른 번호가 만나는 경계선을 미리 칠해놓고 꼭지점에서 DFS 를 수행하는 경우가 있었습니다. polynomeer.log 님의 블로그
N = int(input())
maps = [list(map(int, input().split())) for x in range(N)]
answer = 987654321
for x in range(1, N+1):
    for y in range(1, N+1):
        for d1 in range(1, N+1):
            for d2 in range(1, N+1):
                # out of index
                if x+d1+d2 > N or y-d1 < 1 or y+d2 > N :
                    continue
                is_visited = [ [False] * N for _ in range(N) ]
                # 범위마다 해당하는 요소들 고르기
                arr = [0] * 5
                ## 1번 구역
                ### 직사각형 구역 구하기
                for r in range(1, x):
                    for c in range(1, y+1):
                        arr[0] += maps[r-1][c-1]
                        is_visited[r-1][c-1] = True
                ### 점차 감소하는 부분 구하기
                # (x, 1), (x,2) ,,,, (x, y-1)
                # (x+1, 1), (x+1,2) ,,,, (x+1, y-2)
                # (x+d1-1, 1) ,,,,, (x+d1-1, y - d1)
                search_len = d1
                col_start = y - 1
                row_start = x
                for diff in range(0, search_len):
                    for r, c in [ (row_start+diff, i) for i in range(1, col_start - diff + 1)]:
                        arr[0] += maps[r-1][c-1]
                        is_visited[r - 1][c - 1] = True

                ## 2번 구역
                ### 직사각형 구역 구하기
                for r in range(1, x+1):
                    for c in range(y+1, N+1):
                        arr[1] += maps[r - 1][c - 1]
                        is_visited[r - 1][c - 1] = True
                ### 점차 감소하는 부분 구하기
                search_len = d2
                col_start = y + 2
                row_start = x + 1
                for diff in range(0, search_len):
                    for r, c in [ (row_start + diff, i) for i in range(col_start+diff, N+1)]:
                        arr[1] += maps[r-1][c-1]
                        is_visited[r - 1][c - 1] = True

                ## 3번 구역
                ### 직사각형 구역 구하기
                for r in range(x+d1+d2, N+1):
                    for c in range(1, y+d2-d1):
                        arr[2] += maps[r - 1][c - 1]
                        is_visited[r - 1][c - 1] = True
                ### 점차 감소하는 부분 구하기
                search_len = d2
                col_start = y - d1 + d2 - 2
                row_start = x + d1 + d2 - 1
                for diff in range(0, search_len):
                    for r, c in [ (row_start - diff, i) for i in range(1, col_start - diff + 1)]:
                        arr[2] += maps[r-1][c-1]
                        is_visited[r - 1][c - 1] = True

                ## 4번 구역
                ### 직사각형 구역 구하기
                for r in range(x+d1+d2+1, N+1):
                    for c in range(y+d2-d1, N+1):
                        arr[3] += maps[r - 1][c - 1]
                        is_visited[r - 1][c - 1] = True
                ### 점차 감소하는 부분 구하기
                search_len = d1
                col_start = y-d1+d2+1
                row_start = x+d1+d2
                for diff in range(0, search_len):
                    for r, c in [ (row_start - diff, i) for i in range(col_start + diff, N+1)]:
                        arr[3] += maps[r-1][c-1]
                        is_visited[r - 1][c - 1] = True

                ## 5번 구역
                for r in range(1, N + 1):
                    for c in range(1, N + 1):
                        if is_visited[r - 1][c - 1] == False:
                            arr[4] += maps[r-1][c-1]

                # 정답 갱신
                answer = min(answer, max(arr)-min(arr))
print(answer)