[Python] 21608 - 상어 초등학교, 21609 - 상어 중학교

정환우·2022년 4월 27일
SW 역량테스트python삼성전자
1

코딩 테스트 기출문제

목록 보기
8/14
post-thumbnail

상어 초등학교

  • 난이도 : 실버 1

문제 링크

이게 실버 1 수준까지는 아닌거같은데.. 그래도 골드 4~5 정도는 되는 듯 하다. 암튼, 근데 이렇게 나오면 무조건 2솔이 컷일 것 같다.

나 같은 경우는 자리마다 비어있는 지 여부랑, 인접한 칸 빈칸 개수랑, 그 자리에서 인접한 학생의 번호를 넣어놓고, 완탐을 돌려서 문제 조건에 나와 있는

좋아하는 학생이 인접한 칸에 가장 많은 순 -> 동점이면 인접한 칸 중에 비어있는 칸이 가장 많은 칸 -> 동점이면 행의 번호가 가장 작은 칸 -> 동점이면 열의 번호가 가장 작은 칸

이런식으로 프로세스를 돌렸더니 큰 예외 없이 바로 통과 할 수 있었다.

프로세스

while students:
    # 학생의 번호, 좋아하는 학생의 번호들
    student_num, num1, num2, num3, num4 = students.popleft()
    q = []
    for y in range(N):
        for x in range(N):
            if graph[y][x] != 0:
                continue
            count = 0
            if num1 in adj_graph[y][x]:
                count += 1

            if num2 in adj_graph[y][x]:
                count += 1

            if num3 in adj_graph[y][x]:
                count += 1

            if num4 in adj_graph[y][x]:
                count += 1

            blank = blank_count[y][x]
            heapq.heappush(q, [-count, -blank, y, x])

    count, blank, y, x = heapq.heappop(q)
    graph[y][x] = student_num
    for d in delta:
        ny = y + d[0]
        nx = x + d[1]
        if not check(nx, ny):
            continue
        adj_graph[ny][nx].append(student_num)
        blank_count[ny][nx] -= 1

이것이 완탐을 돌려서 조건 따지고, 선정이 되면 자리 배치후 빈칸이랑 인접한 학생 추가한다.

마지막으로 모든 좌표에 대해서 만족도 조사하면 된다.

전체 코드

from collections import deque
import heapq

N = int(input())

students = deque([])

# N번 학생이 선호하는 친구들 저장
student = [[] for _ in range(N * N + 1)]
for _ in range(N * N):
    inp = list(map(int, input().split()))
    students.append(inp)
    student[inp[0]].append(inp[1:])

# N * N 짜리 격자
graph = [[0 for _ in range(N)] for _ in range(N)]
# 인접한 학생 번호 넣어두기
adj_graph = [[[] for _ in range(N)] for _ in range(N)]
# 인접한 칸
delta = [[-1, 0], [1, 0], [0, 1], [0, -1]]
blank_count = [[0 for _ in range(N)] for _ in range(N)]


def check(x, y):
    if 0 <= x < N and 0 <= y < N:
        return True

    return False


# 빈칸 개수
for y in range(N):
    for x in range(N):
        for d in delta:
            ny = y + d[0]
            nx = x + d[1]
            if not check(nx, ny):
                continue

            blank_count[y][x] += 1

while students:
    # 학생의 번호, 좋아하는 학생의 번호들
    student_num, num1, num2, num3, num4 = students.popleft()
    q = []
    for y in range(N):
        for x in range(N):
            if graph[y][x] != 0:
                continue
            count = 0
            if num1 in adj_graph[y][x]:
                count += 1

            if num2 in adj_graph[y][x]:
                count += 1

            if num3 in adj_graph[y][x]:
                count += 1

            if num4 in adj_graph[y][x]:
                count += 1

            blank = blank_count[y][x]
            heapq.heappush(q, [-count, -blank, y, x])

    count, blank, y, x = heapq.heappop(q)
    graph[y][x] = student_num
    for d in delta:
        ny = y + d[0]
        nx = x + d[1]
        if not check(nx, ny):
            continue
        adj_graph[ny][nx].append(student_num)
        blank_count[ny][nx] -= 1

answer = 0

for y in range(N):
    for x in range(N):
        num = graph[y][x]
        count = 0
        num1, num2, num3, num4 = student[num][0]

        if num1 in adj_graph[y][x]:
            count += 1

        if num2 in adj_graph[y][x]:
            count += 1

        if num3 in adj_graph[y][x]:
            count += 1

        if num4 in adj_graph[y][x]:
            count += 1

        if count == 1:
            answer += 1
        elif count == 2:
            answer += 10
        elif count == 3:
            answer += 100
        elif count == 4:
            answer += 1000

print(answer)

상어 중학교

  • 난이도 : 골드 2

문제 링크

이 문제는 가장 어려웠던게, 블록 그룹 판단하는 거랑 중력 작용하는 부분이었던 것 같다.
중력 작용같은 경우는 카카오 기출문제에서 다뤄본적이 있기 때문에 어렵지 않게 했던 것 같다.
그리고 블록 그룹 같은 경우는 문제 조건을 보면 자세히 나와 있는데,

  • 블록 그룹의 기준 블록은 행의 번호 -> 열의 번호 순서대로 가장 작은 블록
  • 크기가 가장 큰 블록 그룹이 여러개라면 무지개 블록의 수가 가장 많은 블록, 그것도 여러개면 행이 가장 큰것 -> 열이 가장 큰 것

이게 위의 두 조건이 상반되어서, 이 두개를 따질 때 값을 반대로 따지는 게 좀 까다로웠다. 아니 까다롭기보다는 찾기가 굉장히 힘들었다.

그리고 마지막으로 격자 회전 시키는 것, 회전 시키는 것은 진짜 거의 2번에 한번꼴로 나온다. 무조건 숙지해가야 할 것 같다.

격자 회전

# 반시계 방향 90도 회전 
def rotate(g):
    temp = [[0 for _ in range(N)] for _ in range(N)]
    for yy in range(N):
        for xx in range(N):
            temp[N - 1 - xx][yy] = graph[yy][xx]

    return temp

반시계 방향으로 그래프를 회전 시키는 함수이다. (x,y) 값이 반시계 방향으로 회전하면 (y,n-1-x) 로 좌표가 바뀐다.

블록 없애기

def remove_block(start_y, start_x, num):
    global delta
    global graph
    q = []
    visited = [[False] * N for _ in range(N)]
    q.append([start_y, start_x])
    visited[start_y][start_x] = True
    yxlist = [[start_y, start_x]]
    # BFS
    while q:
        cy, cx = q.pop(0)
        for d in delta:
            ny = cy + d[0]
            nx = cx + d[1]
            if not check(ny, nx):
                continue

            if graph[ny][nx] == -1 or visited[ny][nx]:
                continue

            if graph[ny][nx] == 0 or graph[ny][nx] == num:
                visited[ny][nx] = True
                yxlist.append([ny, nx])
                q.append([ny, nx])

    # 블록 지우기
    while yxlist:
        y, x = yxlist.pop()
        graph[y][x] = -2

lazy하게 블록을 지우기 위해 리스트를 이용해서 지울 블록을 저장해 두었다.

중력 작용

def gravitiy():
   global graph

   init_y = N - 1
   for xx in range(N):
       cur_y = init_y
       for _ in range(N - 1):
           if graph[cur_y][xx] == -2:
               for i in range(1, cur_y + 1):
                   if graph[cur_y - i][xx] == -1:
                       break

                   if graph[cur_y - i][xx] != -2:
                       graph[cur_y - i][xx], graph[cur_y][xx] = graph[cur_y][xx], graph[cur_y - i][xx]
                       break
           cur_y -= 1

좌표의 왼쪽 아래서부터 위로 올라가면서 -1이나 빈칸이 아닌 지점을 만날때까지 올라가고, -1을 만나면 탈출, 아니면 바꿔주는 방식으로 했다. 그러면 n^2 안에 해결이 가능하다.

전체 코드

import heapq

N, M = map(int, input().split())
graph = []
for _ in range(N):
   graph.append(list(map(int, input().split())))


# 반시계 방향 90도 회전 
def rotate(g):
   temp = [[0 for _ in range(N)] for _ in range(N)]
   for yy in range(N):
       for xx in range(N):
           temp[N - 1 - xx][yy] = graph[yy][xx]

   return temp


delta = [[-1, 0], [1, 0], [0, 1], [0, -1]]


def check(cy, cx):
   if 0 <= cx < N and 0 <= cy < N:
       return True

   return False


def remove_block(start_y, start_x, num):
   global delta
   global graph
   q = []
   visited = [[False] * N for _ in range(N)]
   q.append([start_y, start_x])
   visited[start_y][start_x] = True
   yxlist = [[start_y, start_x]]
   # BFS
   while q:
       cy, cx = q.pop(0)
       for d in delta:
           ny = cy + d[0]
           nx = cx + d[1]
           if not check(ny, nx):
               continue

           if graph[ny][nx] == -1 or visited[ny][nx]:
               continue

           if graph[ny][nx] == 0 or graph[ny][nx] == num:
               visited[ny][nx] = True
               yxlist.append([ny, nx])
               q.append([ny, nx])

   # 블록 지우기
   while yxlist:
       y, x = yxlist.pop()
       graph[y][x] = -2


def gravitiy():
   global graph

   init_y = N - 1
   for xx in range(N):
       cur_y = init_y
       for _ in range(N - 1):
           if graph[cur_y][xx] == -2:
               for i in range(1, cur_y + 1):
                   if graph[cur_y - i][xx] == -1:
                       break

                   if graph[cur_y - i][xx] != -2:
                       graph[cur_y - i][xx], graph[cur_y][xx] = graph[cur_y][xx], graph[cur_y - i][xx]
                       break
           cur_y -= 1


answer = 0

while True:
   blocks = [[] for _ in range(M + 1)]
   h = []
   block_visit = [[False] * N for _ in range(N)]
   for y in range(N):
       for x in range(N):
           # 검은색 블록이거나, 무지개 블록이거나, 빈칸이거나
           if graph[y][x] == -1 or graph[y][x] == 0 or graph[y][x] == -2:
               continue

           if block_visit[y][x]:
               continue

           q = []
           isvisited = [[False] * N for _ in range(N)]
           block_num = graph[y][x]
           rainbow_count = 0  # 무지개 블록 개수
           block_count = 1  # 사라질 블록 개수
           q.append([y, x])
           isvisited[y][x] = True

           # BFS
           while q:
               cy, cx = q.pop(0)
               for d in delta:
                   ny = cy + d[0]
                   nx = cx + d[1]
                   if not check(ny, nx):
                       continue

                   if graph[ny][nx] == -1 or graph[ny][nx] == -2 or isvisited[ny][nx]:
                       continue

                   if graph[ny][nx] == 0 or graph[ny][nx] == block_num:
                       block_count += 1
                       isvisited[ny][nx] = True
                       if graph[ny][nx] == 0:
                           rainbow_count += 1
                       else:
                           block_visit[ny][nx] = True
                       q.append([ny, nx])
           heapq.heappush(h, [-block_count, -rainbow_count, -y, -x, graph[y][x]])

   if len(h) == 0:
       break
   score, _, y, x, block_num = heapq.heappop(h)
   score = -score
   y = -y
   x = -x

   if score <= 1:
       break
   # 제외할 블록 더하기
   answer += score * score
   remove_block(y, x, block_num)
   gravitiy()
   graph = rotate(graph)
   gravitiy()
print(answer)

나는 이런 조건을 따질때 heapq를 애용하는 편인데, 보면 블록 기준은 맨 왼쪽 위부터 탐색함으로써 가장 작은 y,x값이 담기도록 했고, heapq에는 음수로 넣어줌으로써 pop했을 때 가장 큰 값이 나오도록 했다.

이 부분이 관건이었고, 2문제 모두 푸는데 2시간정도 걸렸다.
복기 끝!

profile
정환우
Hongik CE
이전 포스트

[Python] 21610 - 마법사 상어와 비바리기 ,21611 - 마법사 상어와 블리자드

다음 포스트

[Python] 20057 - 마법사 상어와 토네이도 , 20058 - 마법사 상어와 파이어스톰

0개의 댓글