[코드트리] 예술성(파이썬) 삼성 2022 상반기 코테 기출

https://www.codetree.ai/frequent-problems/artistry/submissions

코드트리

실제로 시험장에서 풀었었던 문제...

그 당시에는 테케 10개 중에서

4개까지만 맞아서

엄청 해매고 써렌쳤던 아픔...

3시간동안 풀거같은데 안풀리는 그 x같음이 잊혀지질 않네요.

 

이 문제를 단계적으로 쪼개보면 이렇습니다.

 

1. BFS로 구역을 구한다

2. 각 경계를 만나는 선분을 구한다

3. 돌려준다

 

제 기억을 되돌아보면

3때문에 시험장에서 뻘짓했습니다.

어라?1~2는 틀린게 없는데...

3이 문제인가...

그렇게 연습장 다 쓰고...

하....

 

이번에 풀 때도 3에서 시간을 많이 써먹긴 했는데

3을 풀 때 좌표를 입력해줬습니다.

#가운데 돌려주기
#가운데 1
for y in range(my):
    new_room[N-1-y][my]=room[mx][y]
    #print(mx,y,N-1-y,my)
#가운데 2
for x in range(N-1,mx,-1):
    new_room[mx][x]=room[x][my]
    #print(x,my,mx,x)

#가운데 3
for y in range(N-1,my,-1):
    new_room[N-1-y][my]=room[mx][y]
    #print(mx,y,N-1-y,my)
#가운데 4
for x in range(mx):
    new_room[mx][x]=room[x][my]
    #print(x,my,mx,x)

이렇게 돌리는 부분에

'이 좌표를 돌리면 어디에 위치하지?'라는 걸 일일이 찍어보면서

직접 다 돌렸습니다.

n=5,7,9 일 때 각각 어떻게 좌표가 돌아가는지 구하고

9까지 맞으면 구현 맞게 한 걸로 넘어갔습니다.

(이런 류의 문제를 풀 때,

테케에서 n=5만 주어졌으니 방심하기 쉬운데

좌표평면 돌아가는 로직이 맞는지 구하려면

n이 그 이상일때도 확인해주는 게 필수)

 

1,2가 은근 골치아픕니다.

정확히는 2입니다.

경계선을 만나는 수인데

이걸 어떻게 시간초과 안나고 정확하게 구할 수 있을까.

저는 미리 리스트에

각 그룹의 좌표

각 그룹의 숫자군

각 그룹의 크기

각 그룹이 마주보는 면

이렇게 4가지를 구했습니다.

 

각 그룹이 마주보는 면은

현재 숫자군과 다른 숫자군을 만날 때입니다.

이렇게 구하면

굳이 모든 구역을 다 돌아가면서

다른 면과 만나는지 안만나는지 볼 필요없이

시간이 훨씬 훨씬 단축됩니다.

해당 면의 구역이 어디인지 파악하고

해당 구역과 마주친 횟수를 리스트에 기록해줍니다.

그리고 이후 공식대로 계산하면 끝.

 

주의할 점은 

'두 경계의 선분'이라는 점.

제가 각 그룹이 마주하는 면을 

집합으로 구했는데

테케 통과가 안되더라고요.

봤더니, 집합으로 구할 때는

들어간 좌표가 겹치면 카운트를 하지 않습니다.

이게 뭐가 문제냐면....

그림을 그려보면 이렇습니다.

nx,ny가 마주보는 면인데

집합으로 구하면 중복이 없어져서

nx,ny 하나만 나옵니다.

이 문제가 

'맞닿는 면'이라고 했으면

집합으로 구하는 게 정답이죠.

하지만 선분을 구해야하는데

저렇게 담으면 맞닿는 선분이

1개로 인식이 되어버립니다.

그래서 저는 리스트로 이걸 돌렸습니다.

 

from collections import deque
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]
N=int(input())

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

answer=[]
for _ in range(4):
    now_socre=0
    #1 bfs
    visited=[[0]*N for _ in range(N)]
    groups=[set()]
    g_face=[[]]
    g_num=[0]
    g_now=[0]
    cnt=1
    for x in range(N):
        for y in range(N):
            if visited[x][y]==0:
                q=deque()
                q.append((x,y))
                now=room[x][y]
                visited[x][y]=cnt
                face=[]
                n_g=set()
                n_g.add((x,y))
                while q:
                    px,py=q.popleft()

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

                        if nx<0 or nx>=N or ny<0 or ny>=N:
                            continue
                        if room[nx][ny]!=now:
                            #처음에는 set를 집합으로 해두었는데
                            #만약 이미 있는 면을 넣으면 선분이 2개가 되더라도 하나가 카운트
                            #그래서 리스트로 바뀌면, 중복은 생긱더라도
                            #한 면에서 각각 들어오는 케이스를 고려하게 됨.
                            face.append((nx,ny))
                            continue

                        if visited[nx][ny]!=0:
                            continue

                        visited[nx][ny]=cnt
                        q.append((nx,ny))
                        n_g.add((nx,ny))

                cnt+=1
                groups.append(n_g)
                g_num.append(len(n_g))
                g_now.append(now)
                g_face.append(face)
    # print(visited)
    # print(groups)
    # print(g_num)
    # print(g_now)
    # print(g_face)
    # print()
    #2 예술점수 구하기

    #어떻게하면 시간초과 안나고
    #제대로 구할까하다가 똥꼬쇼를 했습니다.
    #위의 g_num에는 각 그룹별 길이
    #위의 g_now에는 각 그룹별 숫자군
    #g_face는 맞다아있는 면.
    for i in range(1,len(groups)):
        now_group=groups[i]
        ax,ay=0,0
        for px,py in now_group:
            ax,ay=px,py
            break
        a_num=room[ax][ay]
        a_len=len(now_group)
        f_num=[0]*len(groups)
        for fx,fy in g_face[i]:
            f_g=visited[fx][fy]
            f_num[f_g]+=1


        for k in range(i,len(f_num)):
            if f_num[k]==0:
                continue
            b_num=g_now[k]
            b_len=g_num[k]

            score=(a_len+b_len)*a_num*b_num*f_num[k]
            # print(a_len,a_num,b_len,b_num,f_num[k],score)
            now_socre+=score

    #print(now_socre)
    answer.append(now_socre)
    #3 대망의 돌리기
    #체감상 가장 빡셈. 노가다를 한 나 아이고난!
    mx=N//2
    my=N//2
    new_room=deepcopy(room)
    #90도 회전부터
    #1구역

    for x in range(mx):
        for y in range(my):
            new_room[y][my-x-1]=room[x][y]

    #2구역
    for x in range(mx):
        for y in range(my+1,N):
            new_room[y-my-1][N - x-1] = room[x][y]

    #3구역
    for x in range(mx+1,N):
        for y in range(my):
            new_room[mx+1+y][N - x-1] = room[x][y]
    #4구역
    for x in range(mx+1,N):
        for y in range(my+1,N):
            new_room[N-my+y-N//2-1][N+mx-x] = room[x][y]

    #가운데 돌려주기
    #가운데 1
    for y in range(my):
        new_room[N-1-y][my]=room[mx][y]
        #print(mx,y,N-1-y,my)
    #가운데 2
    for x in range(N-1,mx,-1):
        new_room[mx][x]=room[x][my]
        #print(x,my,mx,x)

    #가운데 3
    for y in range(N-1,my,-1):
        new_room[N-1-y][my]=room[mx][y]
        #print(mx,y,N-1-y,my)
    #가운데 4
    for x in range(mx):
        new_room[mx][x]=room[x][my]
        #print(x,my,mx,x)

    room=deepcopy(new_room)

    # print('nroom')
    # for x in range(N):
    #     for y in range(N):
    #         print(room[x][y],end=' ')
    #     print()
    # print()

# print(answer)
print(sum(answer))

 

디버깅이 많이 빡센 문제.

조낸 피지컬이 필요한 문제인지라

직접 돌려보면서 출력 띄우면서

꼼꼼히 푸시길 응원합니다.