[백준]17822.원판돌리기

문제설명

구현문제.

rotate는 삼성 기출 중 톱니바퀴라는 문제가 있다. 이를 참고하면 좋을 듯.

총 문제 풀이시간은 2시간 10분으로

접근 방법 정하기 및 절차 작성 => 30분소요

구현 1시간 30분 소요

• 첫 코드 작성 40분소요
• rotate 디버깅 30분 소요(;; 절망적.)
• 인접 부분 잘못 고려하여 20분 소요

접근

문제의 큰 틀 접근 자체는 크게 어렵지 않아 보였을 것이다. 그나마 포인트가 될 것은 다음과 같다.

1)인접하다

원형을 단순히 테이블로 변형하여 인접을 고려하는데 큰 어려움이 없을 것이다. 다음 부분만 제외하고.

i번째 원을 기준으로 1번째의 왼쪽인 M번째 수. M번째의 오른쪽인 1번째 수. 이것이 인접하다는 것만 고려해주면 큰 문제는 없다.

2)원판에 동일한 수가 있다면 삭제하는 알고리즘

이는 SWEA의 미생물 문제, 삼성 기출의 미세먼지 문제를 보면 알 수 있는데, board에서 값이 동일하다고 바로 삭제해버리면 안된다. 삭제된 값이 변경되어 그 값과 동일한 것을 삭제 못할 수 있기 때문

• (a,b)와 값이 같은 (a,b-1) 값 삭제(0으로 놨다고 하자.) (a,b-1)은 (a,b-2)와 값이 동일함에도 값을 수정했기 때문에 값이 다르다 판단하여 삭제하지 않아 오류 발생.

이 둘을 지켜주면 된다.

구현

def rotate(circle,k,d,m):
    if d == 0:
        return circle[m-k:]+circle[:m-k]

    else:
        return circle[k:]+circle[:k]

N,M,T = map(int,input().split())
circles = [[0]*M]
totalNumbers = N*M
direction = [[0,1],[0,-1],[1,0],[-1,0]]
for _ in range(N):
    circles.append(list(map(int,input().split())))

for z in range(T):
    x,d,k = map(int,input().split())

    for i in range(1,N+1): #회전
        if i%x == 0 :
            circles[i] = rotate(circles[i],k,d,M)
    #인접탐색
    sumNumbers = 0
    ajflag = False

    delList = set()
    for i in range(1,N+1):
        for j in range(M):
            number = circles[i][j]
            flag = False
            if number == 0:
                continue

            #해당 i,j에 대해 인접 탐색
            for di,dj in direction:
                ni = i+di
                nj = j+dj
                if nj == -1 :
                    nj = M-1
                elif nj == M:
                    nj = 0

                if ni<=0 or ni>N : #i의 0은 수채우기용, N번째까지 존재, j는 0번에서 M-1까지 존재.
                    continue

                ajNumber = circles[ni][nj] #인접 수
                if ajNumber == 0 :
                    continue
                if ajNumber == number: #인접 수가 같다면 삭제해줘야 함. 삭제한다는 것은 0을 의미한다.
                    flag = True
                    delList.add((ni,nj))

            if flag: #삭제가 발생했다면 i,j 위치 삭제해주고 전체 수 삭제
                delList.add((i,j))
                ajflag = True

    if delList:
        for delI,delJ in delList:
            circles[delI][delJ] = 0



    totalNumbers = totalNumbers - len(delList)
    if totalNumbers == 0 :
        break

    sumNumbers = 0
    for i in range(1,N+1):
        sumNumbers+=sum(circles[i])

    avg = sumNumbers/totalNumbers
    if ajflag is False: #삭제가 발생하지 않았다면 평균구해서 가산연산 해줘야 함.
        for i in range(1,N+1):
            for j in range(M):
                if circles[i][j] == 0 :
                    continue
                elif avg>circles[i][j]:
                    circles[i][j] += 1
                elif avg<circles[i][j]:
                    circles[i][j] -= 1
    # 인접탐색
rst = 0
for i in range(1,N+1):
    rst += sum(circles[i])
print(rst)

반성

함수로 작업의 모듈화를 시켜야겠다. input, output 작업에서 call by value를 하는데, 여기서 시간이 좀 더 소요되기 때문에 한 함수 내에서 모두 작업했는데 가독성이 안좋아져서 디버깅도 힘들어진다.

그리고 위 코드는 인접값 탐색시 중복작업이 많아 시간이 오래걸린다.

• (a,b)기준 상하좌우 탐색할 필요없이, r,c를 오름차순으로 탐색한다면 오른쪽과 아래만 탐색해도 모든 탐색이 가능하다. 명심!