[코드트리 챌린지] 5주차 - 기출문제

이번주 또한 807점의 점수로 마무리 할 수 있었다! 다음 주는 꼭 그 이상의 점수를 받는 걸 목표로 잡으면서 다음 주도 화이팅해야겠다.

이번 주는 S 기업 코딩테스트가 예정되어 있어서 대비할 겸 코드트리의 기출 문제를 여러개 풀어보았습니다.

 

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text 

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

 그 중에 올해 상반기 문제 중 1개를 풀며 dx, dy를 활용한 테크닉을 성장시킬 수 있었는데 특히, 배열의 회전을 연습하는데 아주 좋은 문제였습니다

처음엔 모든 격자를 하나씩 돌리는 방법을 사용했다가, zip이라는 내장함수를 활용하여 풀 수 있기에 익숙해지기 위하여 여러 번 풀어봤어요

 

import sys

def finish():
    flag = False
    for i in range(N):
        if flag:
            return flag
        for j in range(N):
            if maze[i][j] < 0:
                flag = True
                break
    return flag


def move():
    global result
    next_l = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if maze[i][j] < 0:
                dist = abs(ei - i) + abs(ej - j)
                for d in range(4):
                    ni, nj = i + di[d], j + dj[d]
                    # 범위 내부이고 사람 또는 빈 칸인 경우에만 이동
                    if 0 <= ni < N and 0 <= nj < N:
                        if maze[ni][nj] <= 0:
                            # 최단 거리 줄었다면 옮길 위치 표시하고 종료
                            if abs(ei - ni) + abs(ej - nj) < dist:
                                next_l[ni][nj] += abs(maze[i][j])
                                result += abs(maze[i][j])
                                break
                        elif maze[ni][nj] == 10:
                            result += abs(maze[i][j])
                            maze[i][j] = 0
                            break
                else:
                    next_l[i][j] += abs(maze[i][j])
    for i in range(N):
        for j in range(N):
            if maze[i][j] < 0:
                maze[i][j] = 0
            if next_l[i][j]:
                maze[i][j] = -next_l[i][j]


def rotate():
    global ei, ej
    # 출구와 참가자 포함되야 되고 r, c 작을 수록 좋음
    # 크기는 최소 2에서 N-1
    # 회전시킬 왼쪽 위, 오른쪽 아래
    li, lj, ri, rj = 0, 0, 0, 0
    flag = False
    for s in range(2, N):
        if flag:
            break
        for i in range(N - s + 1):
            if flag:
                break
            for j in range(N - s + 1):
                if flag:
                    break
                # 사람과 출구 있는지 체크
                check_p, check_e = False, False
                for k in range(i, i + s):
                    if flag:
                        break
                    for u in range(j, j + s):
                        if maze[k][u] < 0:
                            check_p = True
                        elif maze[k][u] == 10:
                            check_e = True

                        if check_e and check_p:
                            flag = True
                            li, lj, ri, rj = i, j, i + s -1, j + s - 1

    temp = []
    for i in range(li, ri+1):
        temp.append(maze[i][lj:rj+1])
    temp = list(zip(*temp[::-1]))
    for i in range(li, ri+1):
        for j in range(lj, rj+1):
            maze[i][j] = temp[i - li][j - lj]
            if 0<maze[i][j]<10:
                maze[i][j] -= 1
            elif maze[i][j] == 10:
                ei, ej = i, j



N, M, K = map(int, input().split())
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]
maze = [list(map(int, input().split())) for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    maze[a - 1][b - 1] += -1

ei, ej = map(int, input().split())
ei-=1
ej-=1
maze[ei][ej] = 10
result = 0

for k in range(K):
    if not finish():
        print(result)
        print(ei + 1, ej + 1)
        break
    move()
    rotate()
else:
    print(result)
    print(ei + 1, ej + 1)

 

- 이외에도 다른 문제들을 풀며 구현 문제를 푸는데 있어 적응력을 키우고 나니 15일 있었던 시험에서 그래도 테스트 케이스는 다 맞추고 나올 수 있었습니다..! 코드트리 쵝오..

 

이번 주도 열심히해서 더 좋은 실력진단 결과로 돌아오겠습니다 :)