[백준 17779번] 게리멘더링2

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

17779번: 게리맨더링 2

문제의 길이가 매우 길므로

게리멘더링에 대해서만 집고 가겠습니다.

저런 식으로 경계를 만드는 건데

규칙은 이렇습니다.

 

저는 이런 순서대로 코드를 구현했습니다.

 

1. 4가지 경계선 먼저 그리기

2. 경계선 안에 5 선거구로 채워넣기

3. 나머지 구역에는 차례대로 1 2 3 4 넣기

 

처음에는

1 2 3 4 선거구를 넣은 다음에

나머지 구역은 선거구 5로 넣는걸로 구현했다가

원래 5로 넣어져야할 부분이

다른 선거구로 채워지는 실수를 범해서

위의 순서대로 코드를 구현했습니다.

어떻게 경계선 안을 채워넣을까 했을 때

BFS에서의 길찾기를 응용하기로 했습니다.

즉, 경계선 안에 있는 좌표를 queue로 받고

5가 아닌 곳에 5를 채우는 식이었죠.

처음에는 지정한 좌표 바로 아래를

(x값-1한 좌표)

큐에 넣고 BFS를 시켜줬습니다.

그러더니 코드가 삐끗했습니다.

바로 아래에

x=2, y=4

d1=2, d2=1

인 케이스가 문제였죠.

이 케이스에서 지정된 좌표 바로 아래를 고르면

하나는 채워넣지 못했습니다.

그래서 다소 복잡하긴 하지만

넣는 케이스를 4가지 추가했습니다.

경계점 1 스타트의 아랫값

경계점 2 스타트의 오른칸

경계점 3 스타트의 윗칸

경계점 4 스타트의 왼칸.

쉽게 생각해서

꼭짓점에서 한 칸 들어간 걸

각각의 좌표로 받았습니다.

물론 중복이 되는 경우에는

당연히 제외를 시키도록 만들었고요

이렇게 만드니 코드가 정상적으로 가동하여

정답을 맞출 수 있었습니다.

 

# 17779 게리멘더링2

from collections import deque

N = int(input())

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

dr = [1, 1, 1, 1]
dc = [-1, 1, 1, -1]  # 1 2 3 4 경계선 규칙에 따라서 정함.

moving_r = [-1, 0, 1, 0]
moving_c = [0, -1, 0, 1]

answer = 1e9

# 모든 점들 각각을 기준점으로 잡고 경계선의 길에 따른  모든 경우를 구해보자
for r in range(N):
    for c in range(N):
        for d_1 in range(1, N // 2):
            for d_2 in range(1, N // 2):

                # 경계선의 범위 설정
                if r + d_1 + d_2 >= N:
                    break

                if c - d_1 < 0:
                    break

                if c + d_2 >= N:
                    break
                one = 0
                two = 0
                three = 0
                four = 0
                five = 0

                visited = [[0] * N for _ in range(N)]
                visited[r][c] = 5
                five += A[r][c]

                # print(r,c,d_1,d_2)

                # 1번 경계선
                time = 0
                one_r = r
                one_c = c
                if not visited[one_r][one_c]:
                    visited[one_r][one_c] = 5
                    five += visited[one_r][one_c]

                while time < d_1:
                    one_r += dr[0]
                    one_c += dc[0]
                    if (one_r < 0 or one_r >= N) or (one_c < 0 or one_c >= N):
                        break
                    if not visited[one_r][one_c]:
                        visited[one_r][one_c] = 5
                        five += A[one_r][one_c]

                    time += 1

                # 2번 경계선
                time = 0
                two_r = r
                two_c = c

                if not visited[two_r][two_c]:
                    visited[two_r][two_c] = 5
                    five += visited[two_r][two_c]

                while time < d_2:
                    two_r += dr[1]
                    two_c += dc[1]
                    if (two_r < 0 or two_r >= N) or (two_c < 0 or two_c >= N):
                        break
                    if not visited[two_r][two_c]:
                        visited[two_r][two_c] = 5
                        five += A[two_r][two_c]

                    time += 1

                # 3번 경계선
                time = 0
                three_r = r + d_1
                three_c = c - d_1

                if not visited[three_r][three_c]:
                    visited[three_r][three_c] = 5
                    five += visited[three_r][three_c]

                while time < d_2:
                    three_r += dr[2]
                    three_c += dc[2]
                    if (three_r < 0 or three_r >= N) or (three_c < 0 or three_c >= N):
                        break
                    if not visited[three_r][three_c]:
                        visited[three_r][three_c] = 5
                        five += A[three_r][three_c]

                    time += 1

                # 4번 경계선

                time = 0
                four_r = r + d_2
                four_c = c + d_2
                if not visited[four_r][four_c]:
                    visited[four_r][four_c] = 5
                    five += visited[four_r][four_c]

                while time < d_1:
                    four_r += dr[3]
                    four_c += dc[3]
                    if (four_r < 0 or four_r >= N) or (four_c < 0 or four_c >= N):
                        break
                    if not visited[four_r][four_c]:
                        visited[four_r][four_c] = 5
                        five += A[four_r][four_c]

                    time += 1

                # 5번 선거구를 먼저 지정
                # 1번째 스타트의 아랫칸, 2번째 스타트의 오른칸,
                # 3번째 스타트의 윗칸, 4번째 스타트의 왼칸
                # 이렇게를 불러온다
                q = deque()

                m_r = r + 1
                m_c = c
                if not visited[m_r][m_c]:
                    visited[m_r][m_c] = 5
                    five += A[m_r][m_c]
                    q.append((m_r, m_c))

                m_r = r + d_2
                m_c = c + d_2 - 1
                if not visited[m_r][m_c]:
                    visited[m_r][m_c] = 5
                    five += A[m_r][m_c]
                    q.append((m_r, m_c))

                m_r = r + d_1
                m_c = c - d_1 + 1
                if not visited[m_r][m_c]:
                    visited[m_r][m_c] = 5
                    five += A[m_r][m_c]
                    q.append((m_r, m_c))

                m_r = r + d_1 + d_2 - 1
                m_c = c - d_1 + d_2
                if not visited[m_r][m_c]:
                    visited[m_r][m_c] = 5
                    five += A[m_r][m_c]
                    q.append((m_r, m_c))
                # 칸이 위치 탐색을 상하좌우로 하면서 채워나감
                while q:
                    n_r, n_c = q.popleft()
                    for i in range(4):
                        go_r = n_r + moving_r[i]
                        go_c = n_c + moving_c[i]
                        if (go_r < 0 or go_r >= N) or (go_c < 0 or go_c >= N):
                            break
                        if not visited[go_r][go_c]:
                            visited[go_r][go_c] = 5
                            five += A[go_r][go_c]
                            q.append((go_r, go_c))

                # 1 2 3 4번 선거구를 지정

                # 1번 선거구
                for x in range(0, r + d_1):
                    for y in range(0, c + 1):
                        if not visited[x][y]:
                            one += A[x][y]
                            visited[x][y] = 1

                # 2번 선거구
                for x in range(0, r + d_2 + 1):
                    for y in range(c + 1, N):
                        if not visited[x][y]:
                            two += A[x][y]
                            visited[x][y] = 2

                # 3번 선거구

                for x in range(r + d_1, N):
                    for y in range(0, c - d_1 + d_2):
                        if not visited[x][y]:
                            three += A[x][y]
                            visited[x][y] = 3

                # 4번 선거구
                for x in range(r + d_2 + 1, N):
                    for y in range(c - d_1 + d_2, N):
                        if not visited[x][y]:
                            four += A[x][y]
                            visited[x][y] = 4

                # print(one,two,three,four,five)
                min_po = min(one, two, three, four, five)
                max_po = max(one, two, three, four, five)
                now_po = max_po - min_po
                # print(now_po)
                answer = min(answer, now_po)
print(answer)

이 문제는 부피가 크다보니

디버깅하는 게 조금 빡셌습니다.

저는 디버깅을 할 떄

r c d1 d2를 다 받고

어라?이거 왜 값이 이상하지?

하면 해당 r c 값에 대해서

if r==.... and c==....

이런 식으로 해서

제가 원하는 값만을 보도록 출력했습니다.

저는 선거구 5를 만들 때

경계선을 만들고

채워넣는다는 식으로 접근했는데

구글링해본 결과

아예 이동할 때 채우신 분들도 많았습니다.

저처럼 바로 대각선으로 이동한 게 아닌

x y축 각각 이동하면서

차례대로 넣는 방식이었습니다.

코드를 실제로 구현한 결과

그 방식이 더 간단하긴 합니다.

이 방식은 노가다를 좀 해야하는 단점이...ㅎ

 

 

+++++

 

경계선을 만들고 채워넣는 방식도 가져와봤습니다.

 

https://pacific-ocean.tistory.com/382

[백준] 17779번(python 파이썬)

해당 솔루션을 저의 식대로 바꾸었습니다.

다른 점이라면, 이 분은 간단하게

행렬을 1부터 N까지 냅두었다면

저는 0부터 N-1까지 냅두었습니다.

여기서 주의할 점은

5를 채워넣는 부분입니다.

해당 코드에서는

맨 위 경계선점 바로 아래행부터

맨 아래 경계선점 바로 윗행까지를

5로 채워넣는 개념으로 접근했습니다.

만약에 경계선 처음부터 마지막까지하면

경계선 이후에 5555555가 계속 더해져서

범위가 이상하게 되는 불상사가 발생합니다.

(범위는 프로그래밍의 생명이다)

 

# 백준 177779번 게리맨더링2

N = int(input())

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

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

max_result = 100000000

for x in range(N):
    for y in range(N):
        for d1 in range(1, N):
            for d2 in range(1, N):
                if 0 <= x + d1 + d2 <= N - 1 and 0 <= y - d1 < y < y + d2 <= N - 1:

                    temp = [[0] * N for _ in range(N)]
                    cal = [0 for i in range(5)]

                    # 5경계선

                    for i in range(d1 + 1):
                        temp[x + i][y - i] = 5
                        temp[x + d2 + i][y + d2 - i] = 5

                    for i in range(d2 + 1):
                        temp[x + i][y + i] = 5
                        temp[x + d1 + i][y - d1 + i] = 5
                    # 5의 구역 넣기
                    # 경계선 아랫행부터 채운다
                    # 경계선부터 체우면 뒤를 555555로 채우는 불상사 발생.
                    for i in range(x + 1, x + d1 + d2):
                        isTrue = False
                        for j in range(N):
                            if temp[i][j] == 5:
                                isTrue = not isTrue
                            if isTrue: temp[i][j] = 5
                    # 모든 구역 인구수
                    for r in range(N):
                        for c in range(N):
                            if r < x + d1 and c <= y and temp[r][c] == 0:
                                cal[0] += A[r][c]
                            elif r <= x + d2 and y < c and temp[r][c] == 0:
                                cal[1] += A[r][c]
                            elif x + d1 <= r and c < y - d1 + d2 and temp[r][c] == 0:
                                cal[2] += A[r][c]
                            elif x + d2 < r and y - d1 + d2 <= c and temp[r][c] == 0:
                                cal[3] += A[r][c]
                            elif temp[r][c] == 5:
                                cal[4] += A[r][c]
                    now_result = max(cal) - min(cal)
                    max_result = min(max_result, now_result)

print(max_result)

 

 

시간측면에서는 위의 코드가 더 짧긴한데

가독성 측면에서는 아래코드가 더 좋았습니다.

최대한 문제대로 코드를 구현하는 것이

프로그래머 입장에서 더 생각이 정리가 잘 될 듯 합니다.

 

(내용추가-2022.10.13)

from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]

N=int(input())
room=[list(map(int,input().split())) for _ in range(N)]
answer=1e9
def inside(num):
    if num<0 or num>=N:
        return False
    return True


def geree(x,y,d1,d2):
    global answer
    board=[[0]*N for _ in range(N)]
    #print('start',x,y,d1,d2)
    hap=[0,0,0,0,0,0]
    #구역을 나누고 각 구역의 인구수 더하기
    #5구역 나눌 때, 안의 넣을거 구해주기
    tmp=set()
    ha=set()
    #print('one')
    for d in range(0,d1+1):
        nx=x+d
        ny=y-d
        board[nx][ny]=5
        ha.add((nx,ny))
        if d>=1:
            tmp.add((nx,ny+1))
        #print(nx,ny)

    #print('two')
    for d in range(0,d2+1):
        nx=x+d
        ny=y+d
        board[nx][ny]=5
        ha.add((nx, ny))
        if d>=1:
            tmp.add((nx,ny-1))
        #print(nx,ny)

    #print('three')
    for d in range(0,d2+1):
        nx=x+d1+d
        ny=y-d1+d
        board[nx][ny]=5
        ha.add((nx, ny))
        if d<d2:
            tmp.add((nx,ny+1))
        #print(nx,ny)

    #print('four')
    for d in range(0,d1+1):
        nx=x+d2+d
        ny=y+d2-d
        board[nx][ny]=5
        ha.add((nx, ny))
        if d<d1:
            tmp.add((nx,ny-1))
        #print(nx,ny)

    #5구역 인구수
    q=deque()

    for tx,ty in tmp:
        q.append((tx,ty))



    while q:
        px,py=q.popleft()
        board[px][py]=5
        ha.add((px, py))


        for d in range(4):
            nx=px+dx[d]
            ny=py+dy[d]

            if board[nx][ny]==5:
                continue

            q.append((nx,ny))
            board[nx][ny]=5

    for tx,ty in ha:
        hap[5]+=room[tx][ty]
    #나머지 구역들
    #1구역
    for nx in range(0,x+d1):
        for ny in range(0,y+1):
            if board[nx][ny]==5:
                break
            board[nx][ny]=1
            hap[1]+=room[nx][ny]

    #2구역
    for nx in range(0,x+d2+1):
        for ny in range(N-1,y,-1):
            if board[nx][ny]==5:
                break
            board[nx][ny]=2
            hap[2]+=room[nx][ny]
    #3구역
    for nx in range(x+d1,N):
        for ny in range(0,y-d1+d2):
            if board[nx][ny]==5:
                break
            board[nx][ny]=3
            hap[3]+=room[nx][ny]

    #4구역
    for nx in range(x+d2+1,N):
        for ny in range(N-1,y-d1+d2-1,-1):
            if board[nx][ny]==5:
                break
            board[nx][ny]=4
            hap[4]+=room[nx][ny]

    # if x==3 and y==2 and d1==1 and d2==1:
    #     for k in range(N):
    #         print(board[k])

    ma_p=max(hap[1:])
    mi_p=min(hap[1:])
    n_cha=ma_p-mi_p

    answer=min(answer,n_cha)







for x in range(N):
    #y좌표가 1~N-2일때를 보셔도 무방함. 킹냐. 0이나 N-1일때는 d1이든 d2든 1이 되면 범위를 벗어나서 어처피 못한다
    for y in range(1,N-1):
        for d1 in range(1,N):
            for d2 in range(1,N):
                if not inside(x+d1) or not inside(x+d2) or not inside(y-d1) or not inside(y+d2) or not inside(x+d1+d2):
                    break
                geree(x,y,d1,d2)

print(answer)

이번에는 시간을 더 줄여보기 위해서

게리멘더링 좌표 구하는 것부터 손을 봤습니다.

우선, 생각해보니 굳이 모든 좌표를 구할 필요없고

y좌표는 0과 N-1를 건너뛰어도 무방합니다.

왜냐하면 행 양끝단에서는 d1,d2가 1이 되면 무조건 범위를 벗어나기 때문이죠.

(추가적으로 x좌표도 0~N-1까지 탐방해도 무방하긴 하던데

백준에서 python으로 제출했을 땐 N-1까지 탐색했을때가 시간이 약간 더 걸린다고 뜨긴합니다)

 

게리멘더링 좌표를 구하면, 경계선을 먼저 만들어줍니다.

이때, 경계선 안을 queue안에 넣는 작업을 합니다.

저는 집합을 만들어주어서

중복이 되는 케이스도 자연적으로 해결했습니다.

여기서 주의할 점은!!!

1,2 케이스는 d>=1이상부터

3,4 케이스는 d가 끝점 전까지

경계를 넣어주는 점.

1,2,의 처음 시작점은 x,y인데

저 조건을 안 넣어주면

시작점 왼쪽,오른쪽 좌표도 넣어줘서 이상하게 되더라고요.

그리고 3,4는 마지막이 꼭지점인데

마지막까지 넣어주면 그 꼭지점 좌우도 받게 됩니다.

경계선 안 쪽 채워주는 부분에서

계속 범위초과 오류가 떠서 살펴보니 이 점이 문제였습니다.

그 이후에는 1,2,3,4도 범위대로 구한 후에 값을 더해주면 됩니다.

(디버깅이 조금 어렵게 느껴질 수 있는데요.

저는 예제의 케이스를 직접 출력해보면서 디버깅했습니다.

문제설명에서 x=2,y=4,d1=2,d2=2일 때 범위가 나와서

저도 이거에 맞춰서 

'이때의 범위칠해주는 게 어떻게 되는지'출력했습니다.)

 

여기서 주의할 점은

5의 인구수를 구하는 부분.

저는 중복을 피하기 위해

경계선+경계선 안을 집합으로 전부 받은 뒤에

다 채운 후 하나씩 꺼내서 더해줬습니다.