[코드트리] 삼성 SW 역량테스트 2022 상반기 오전 2번 문제 - 예술성

코딩테스트를 준비하기위해 모의 기출을 풀어보았다. 

 

코드트리 - 삼성 SW 역량테스트 2022 상반기 오전 2번 문제 / 문제번호 : 예술성 / 문제 유형 : BFS, 구현 / 골드 3

https://www.codetree.ai/training-field/frequent-problems/artistry/description?page=3&pageSize=20&username=haen1231&tier=&tags=&statuses=&order= 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제가 길기에 정확한 문제는 위의 사이트에서 확인하면 된다.

 

일단, 문제를 해결하기 위해 접근한 단계는 다음과 같다.

 

Solution

1. BFS
2. 예술점수 구하기
3. 회전

1. BFS

우선, 입력한 정보를 graph 변수에 넣어준다.

이후, BFS를 통해 그룹인 것을 확인해 주었다. 이때, 같은 값을 가진 그룹이 있을 수 있기에 이를 구분해주기 위해 group_num이라는 변수를 넘겨주었고,  graph와 별도로 group이라는 배열을 만들어 값이 아닌 그룹으로 정보를 저장해 두었다.

 

 

graph가 위와 같다면, 내가 만들어준 group은 회색으로 표시된 G4의 안의 값이 4로 들어있다고 생각하면 된다.

또한, 나중에 겹쳐있는 변을 구해야 하므로 group_data라는 배열을 만들어 주었다.

group_data는 각 그룹마다 (값, 개수, [인접한 숫자 좌표])가 저장되어 있다. 

인접한 숫자 좌표는, BFS 함수에서 상하좌우를 돌면서 인접한지 확인할 때, 같은 값을 가지고 있지 않으면 ( = 다른 그룹) 배열에 저장한다.

 

2.  예술점수 구하기

문제에서 보면, 조화로움을 구하는 것은 

(그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수 

라고 되어있다. 

 

문제를 풀면서 처음으로 고민했던 부분은, 인접한 부분을 어떻게 계산할지 였다. 이를 해결하기 위해 group_data와 group을 만들었다. 

 

 

2.1 변의 개수 구하기

 

변의 개수를 구하는 함수 findsidenum을 만들어 주었고, 이 함수는 현재의 그룹 번호와 원하는 그룹 번호를 인자로 넣는다.

group_data를 통해 현재 그룹과 인접한 숫자 좌표들을 받고,

이를 group에다 넣어 몇번째 그룹에 해당하는 좌표인지 확인한다.

 

이 작업은 딕셔너리로 하여 각 그룹마다 닿아있는 좌표의 개수를 구한다. 이 개수가 바로 맞닿아있는 변의 숫자이다.

 

그리고 이 변의 수를 통해 조화로움을 계산하는 findjohwa를 구현하였다.(작명센스무엇,,,,)

 

2.2 예술점수 구하기

 

예술점수는 각 쌍의 조화로움을 더한 수이다. 그러나 어떤 쌍이 서로 맞닿아있는지 확인하기 어렵기에 나는 모든 쌍을 확인해 주었다. 

for문을 이용해 0~3까지의 그룹의 쌍을 구했다. ( (1,0),(2,0),(2,1),(3,0),(3,1),(3,2) 이런식으로 )

 

각 그룹이 서로 맞닿아 있지 않아도, 맞닿아 있는 변의 수가 0 이기에 예술점수에 포함되지 않는다.

 

3. 회전

이 문제에서 가장 고민한 부분이다. 

문제에서의 회전은 여태까지 다른 문제들과 달리 가운데 십자 부분과 나머지 부분의 회전이 서로 달랐다.

 

위와 같이 십자는 반시계방향, 나머지부분은 시계방향으로 회전한다.

 

따라서 graph에서 나머지 부분을 뽑아왔고, 이를 시계방향으로 회전 시켰다.

시계방향 회전은 zip을 이용하자.

 

참고로,

 

- 시계방향 회전(90도)

A = list(map(list, zip(*arr[::-1])))
# [[19, 13, 7, 1], [20, 14, 8, 2], [21, 15, 9, 3], [22, 16, 10, 4]]

- 반시계방향 회전(90도)

B = list(map(list, zip(*arr)))[::-1]
# [[4, 10, 16, 22], [3, 9, 15, 21], [2, 8, 14, 20], [1, 7, 13, 19]]

이다.

 

마찬가지로 위의 코드를 이용해 십자모양을 추출해 반시계방향 회전을 시켜주었다.

 

이후 이 회전한 배열들을 하나로 합쳐주었는데, 처음에는 이 부분에서 오류가 났었다.

 

이렇게 회전함수까지 완성시켜주면 아래와 같은 코드가 완성된다.

 

 

정답 코드

from collections import deque
from collections import defaultdict

N = int(input())

gragh = []
direction = [(0,1),(0,-1),(1,0),(-1,0)]
answer = 0

for _ in range(N):
    gragh.append(list(map(int,input().split())))

def bfs(s_i,s_j,group_num,gragh,visited,group,group_data):
    data = []
    now = gragh[s_i][s_j]
    visited[s_i][s_j] = True
    group[s_i][s_j] = group_num
    num = 1
    queue = deque([(s_i,s_j)])
    while queue:
        x,y = queue.popleft()
        for d in direction:
            (dx,dy) = d
            nx,ny = x+dx,y+dy
            if 0<=nx<N and 0<=ny<N:
                if gragh[nx][ny] == now and not visited[nx][ny]:
                    visited[nx][ny] = True
                    group[nx][ny] = group_num
                    num += 1
                    queue.append((nx,ny))
                elif gragh[nx][ny] != now:
                    data.append((nx,ny))
    group_data.append((now,num,data))
    
# 변 구하기
# group : 0 1 2 3
def findsidenum(now,want):
    group_dic = defaultdict(int)
    for g in group_data[now][2]:
        g_x,g_y = g
        group_dic[group[g_x][g_y]] += 1
    return group_dic[want]

def findjohwa(g1, g2, group_data):
    score = (group_data[g1][1] + group_data[g2][1]) * group_data[g1][0] * group_data[g2][0] * findsidenum(g1,g2)
    return score

#예술점수    
def findscore(group_data):
    num = 0
    limit = len(group_data)
    for i in range(limit):
        for j in range(i):
            num += findjohwa(j,i,group_data)  
    return num              


#회전
def lotation(gragh,N):
    row = N//2
    #십자모양 제외 시계방향 90
    new_gragh1 = list(map(list,zip(*[l[0:row] for l in gragh[0:row]][::-1])))
    new_gragh2 = list(map(list,zip(*[l[row+1:] for l in gragh[0:row]][::-1])))
    new_gragh3 = list(map(list,zip(*[l[0:row] for l in gragh[row+1:]][::-1])))
    new_gragh4 = list(map(list,zip(*[l[row+1:] for l in gragh[row+1:]][::-1])))

    #십자모양 반시계 90
    mid_l = list(map(list,zip(*[l[0:row] for l in gragh[row:row+1]])))[::-1]
    mid_b = list(map(list,zip(*[l[row:row+1] for l in gragh[row+1:]])))[::-1]
    mid_r = list(map(list,zip(*[l[row+1:] for l in gragh[row:row+1]])))[::-1]
    mid_t = list(map(list,zip(*[l[row:row+1] for l in gragh[0:row]])))[::-1]

    mid_t[0].append(gragh[row][row])

    for i in range(row):
        new_gragh1[i].append(mid_r[i][0])
        new_gragh3[i].append(mid_l[i][0])
        mid_t[0].append(mid_b[0][i])
        for j in range(row):
            new_gragh1[i].append(new_gragh2[i][j])
            new_gragh3[i].append(new_gragh4[i][j])
    
    new = []
    for i in range(row):
        new.append(new_gragh1[i])
    
    new.append(mid_t[0])
    
    for i in range(row):
        new.append(new_gragh3[i])
    
    return new


for t in range(4):
    visited = [[False]*N for _ in range(N)]
    group = [[-1]*N for _ in range(N)]
    group_data = [] # 그룹정보 - value, num
    group_num = 0

    if t != 0:
        gragh = lotation(gragh,N)
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                bfs(i,j,group_num,gragh,visited,group,group_data)
                group_num += 1
    answer+=findscore(group_data)

print(answer)