코드트리 예술성 | python | bfs 그룹별 정보 담기 | 회전 규칙 찾기

Konseo·2023년 10월 11일
0

코테풀이

목록 보기
45/59

문제

링크

풀이

정답률보고 만만하게 봤으나 결코 그렇게 만만하진 않았던 문제이다. 구현 아이디어를 잘 떠올려야 빠르게 풀 수 있는 문제. 그래도 최근 기출 문제 중에서는 쉬운 편에 속하는 것 같고 제약조건이 많지 않아서 테케만 맞추면 무난하게 정답을 도출해낼 수 있는 문제였던 것 같다 (디버깅을 안해서 너무 행복했다)

해당 문제에서의 key point
1. 두 그룹 간 서로 맞닿아 있는 변의 수를 어떻게 구하는가?
2. 십자가, 그리고 부분 정사각형 회전을 어떻게 하는가?
이다. 아래에서 각 포인트에 대해 간략히 살펴보자

1. 두 그룹 간 서로 맞닿아 있는 변의 수 구하기

먼저 동일한 숫자가 상하좌우로 인접해있는 경우를 동일한 그룹으로 본다고 가정했을 때 이를 그룹핑하는 것은 bfs()로 쉽게 처리할 수 있다.

이 때 bfs() 과정 중에 그룹 별 정보 (= [그룹의 독립적인 ID(Num), 그룹을 이루고 있는 숫자 값, 그룹에 속한 칸의 수])를 group 이란 배열에 저장해둔다

def bfs(i,j,groupNum,visited,boardNum):
    coordinate=[]
    q=deque()
    q.append((i,j))
    visited[i][j]=1
    coordinate.append((i,j))
    while q:
        y,x = q.popleft()
        for dy, dx in d:
            Y=dy+y
            X=dx+x
            if 0<=Y<N and 0<=X<N and not visited[Y][X] and board[Y][X]==boardNum:
                visited[Y][X]=1
                q.append((Y,X))
                coordinate.append((Y,X))
    cnt=len(coordinate)
    for y,x in coordinate:
        group[y][x]=[groupNum,boardNum,cnt]

bfs()을 통해 그룹핑 및 그룹별 정보를 기록한 group 배열을 완성시켰다면 그룹 간 맞닿아 있는 변의 수를 구해 조화로움 점수를 계산해보자. -> getPoints()

먼저, 비교할 그룹 2개를 찾기 위해 combinations 함수를 만들어주고 checkGroupLine 함수를 호출한다.

def getPoints():
    global groupNum,comb
    arr=[i for i in range(1,groupNum+1)]
    # 그룹 조합을 찾는다
    comb=[]
    combinations(2,[],0,arr)
    for c in comb:
        group1,group2=c
        checkGroupLine(group1,group2)
def checkGroupLine(group1Num,group2Num):
    global total_points
    q = deque()
    group1Info=[]
    group2Info=[]
    lineNum = 0
    visited = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if group[i][j][0]==group1Num: # 조건 닿으면 바로 함수 return
                group1Info=group[i][j]
                # 그룹 간 인접한 변을 찾기 위한 bfs 수행 시작
                q.append((i,j))
                visited[i][j]=1
                while q:
                    y,x = q.popleft()
                    for dy, dx in d:
                        Y=y+dy
                        X=x+dx
                        if 0<=Y<N and 0<=X<N and not visited[Y][X]:
                            if group[Y][X][0]==group1Num:
                                visited[Y][X]=1
                                q.append((Y,X))
                            elif group[Y][X][0]==group2Num:
                                group2Info=group[Y][X]
                                # visited[Y][X] = 1
                                lineNum+=1
                if lineNum>0:
                    total_points+=(group1Info[2]+group2Info[2])*group1Info[1]*group2Info[1]*lineNum
                return

checkGroupLine 함수의 매개변수로 두 그룹을 받는다.
맞닿은 변을 찾기 위해 또 한 번 bfs 로직을 사용할 건데, 이 때 하나의 그룹을 기준으로 bfs를 돌려야만 맞닿은 변을 중복없이 정확하게 계산할 수 있다.

bfs 로직은 기본 로직과 동일하지만, 큐에 좌표를 넣을지 결정하는 조건 부분에서 이동하려는 칸이 또 다른 그룹의 칸이라면 lineNum 변수를 1 증가시키는 코드를 추가해주면 된다.

bfs 로직이 끝나면 바로 조화로움 점수를 계산해주면 끝 !

2. 십자가 모양 및 부분 정사각형 회전시키기

이건 사실 별도의 알고리즘이 필요한게 아니라서 규칙을 찾아내기만 하면 쉽게 구현할 수 있는 파트이다. 평소 회전하는 코드를 익혀두면 빠르게 풀 수 있을 것이다.

코드

import copy
from collections import deque
N=int(input())
board=[]
for _ in range(N):
    board.append(list(map(int,input().split())))

group=[[[0,0,0] for _ in range(N)] for _  in range(N)] # groupNum, 해당 그룹을 이루고 있는 숫자 값, 전체 변의 개수

d=[(0,-1),(0,1),(1,0),(-1,0)]
def bfs(i,j,groupNum,visited,boardNum):
    coordinate=[]
    q=deque()
    q.append((i,j))
    visited[i][j]=1
    coordinate.append((i,j))
    while q:
        y,x = q.popleft()
        for dy, dx in d:
            Y=dy+y
            X=dx+x
            if 0<=Y<N and 0<=X<N and not visited[Y][X] and board[Y][X]==boardNum:
                visited[Y][X]=1
                q.append((Y,X))
                coordinate.append((Y,X))
    cnt=len(coordinate)
    for y,x in coordinate:
        group[y][x]=[groupNum,boardNum,cnt]



# 현재 인덱스를 매개변수로 계속 넘겨주어야함
# 순서가 상관없기 때문에 현재 인덱스보다 낮은 인덱스 값은 볼 필요가 없기 때문
comb=[]
def combinations(n, new_arr, cur_idx,origin):
    # 순서 상관 X, 중복 X
    if len(new_arr) == n:
        comb.append(new_arr)
        return
    for i in range(cur_idx, len(origin)):
        combinations(n, new_arr + [origin[i]], i + 1,origin)

total_points=0
def checkGroupLine(group1Num,group2Num):
    global total_points
    q = deque()
    group1Info=[]
    group2Info=[]
    lineNum = 0
    visited = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if group[i][j][0]==group1Num: # 조건 닿으면 바로 함수 return
                group1Info=group[i][j]
                # 그룹 간 인접한 변을 찾기 위한 bfs 수행 시작
                q.append((i,j))
                visited[i][j]=1
                while q:
                    y,x = q.popleft()
                    for dy, dx in d:
                        Y=y+dy
                        X=x+dx
                        if 0<=Y<N and 0<=X<N and not visited[Y][X]:
                            if group[Y][X][0]==group1Num:
                                visited[Y][X]=1
                                q.append((Y,X))
                            elif group[Y][X][0]==group2Num:
                                group2Info=group[Y][X]
                                # visited[Y][X] = 1
                                lineNum+=1
                if lineNum>0:
                    total_points+=(group1Info[2]+group2Info[2])*group1Info[1]*group2Info[1]*lineNum
                return
def getPoints():
    global groupNum,comb
    arr=[i for i in range(1,groupNum+1)]
    # 그룹 조합을 찾는다
    comb=[]
    combinations(2,[],0,arr)
    for c in comb:
        group1,group2=c
        checkGroupLine(group1,group2)

def plus_rotate(): # 십자가 모양 반시계 방향 회전

    for i in range(N):
        for j in range(N):
            if i == half:
                arr[i][j] = board[j][i]
            if j == half:
                arr[i][j] = board[N-j-1][N-i-1]


def square_rotate(x, y, l): # 부분 정사각형 회전

    for i in range(x, x+l):
        for j in range(y, y+l):
            ox, oy = i - x, j - y # (0, 0)으로 변환

            rx, ry = oy, l - ox - 1 # 시계 방향 회전 규칙

            arr[rx + x][ry + y] = board[i][j] # 다시 (x,y)를 더해줌


for _ in range(4):
    visited=[[0]*N for _ in range(N)]
    groupNum=0
    # bfs 돌면서 그룹 생성 및 그룹 별 정보를 group 배열에 담기
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                groupNum+=1
                bfs(i,j,groupNum,visited,board[i][j])
    getPoints()

    arr = [[0] * N for _ in range(N)]  # 배열 회전하기 위해 만든 빈 배열
    half = N // 2

    plus_rotate()

    square_rotate(0, 0, half)
    square_rotate(0, half + 1, half)
    square_rotate(half + 1, 0, half)
    square_rotate(half + 1, half + 1, half)

    board=copy.deepcopy(arr)
print(total_points)

갑자기 풀면서 느낀건데 뭔가 직사각형 회전하는 문제가 나올 것 같다 . .

profile
둔한 붓이 총명함을 이긴다

0개의 댓글