알고리즘 풀이 백준(BOI) 17822) 원판 돌리기 (Python)

백준(BOI) 17822 - 원판 돌리기

---

 

 

17822번: 원판 돌리기

 

[ 문제풀이 ]

 

  숫자가 적혀있는 원판을 지시대로 돌리면서 어떤 숫자와 인접한 숫자가 존재할 경우 그 숫자는 지워준다. 인접하는 두 개 이상의 숫자가 하나라도 존재하지 않을 경우 판에 남아있는 숫자들의 평균값을 구해 평균보다 작은 숫자엔 +1을 큰 숫자엔 -1을 한다. 이후 판을 모두 돌리고 난 후의 판에 남아있는 숫자들을 전부 더해 결과를 출력하는 문제이다.

 

 이 문제는 배열의 회전과 인접한 숫자들의 체크만 잘해주면 별 무리 없이 통과할 수 있는 문제이다.

 

 필자는 78% 부근에서 런타임 에러를 겪었는데 함정이 하나 존재한다.(사실 생각해보면 함정도 아니다)

 

메모리와 시간이 여유 있게 주어지므로 지시하는 대로 구현만 잘해주면 된다. 특수한 기법이나 기똥찬 방법을 쓰지는 않았다.

 

먼저 문제에서 주어진 로직은 다음과 같다.

 

 

1. 원판을 회전시킨다.

 입력으로 x, d, k가 주어진다. x의 배수에 해당되는 원판 전부를 모두 k번만큼 d(0 : 시계, 1 : 반시계) 방향으로 회전시키면 된다.

 

 필자는 원판을 2차원 배열로 받았고 시계방 향일 경우 0번 인덱스를 temp 변수에 저장해놓고 4번 인덱스부터 3번 인덱스를 4번 인덱스에 복사하는 방식으로 구현했다. (반시계 방향은 마지막 인덱스를 저장해놓고 방향만 반대로)rotate() 메소드가 이를 구현한 코드다, targetList는 rotate()를 호출하기 전 x의 배수를 구해주는 calcTarget() 함수의 결과로 받은 배열이다.

 

2. 회전이 완료된 원판에서 인접한 숫자가 있는지 체크한다.

 checkGrid() 메소드에 구현하였으며, 그리드의 모든 부분을 대상으로 값이 -1이 아닐 경우 좌표를 매개변수로 하여 해당 함수를 호출한다.  해당 함수에서는 받은 좌표값을 큐에 넣어주고 이후 방향을 탐색하면 된다. 필자는 원판을 2차원 배열에 구현하였으니 이에 주의하여 탐색을 하여야 한다. 

 

 다음은 2차원 배열에 원판을 구현하였을 경우 필자가 주의한 사항이다. 

• 열(칼럼)을 이동할 때에는 끝과 처음으로 이동이 가능하다. 즉 인덱스가 len(grid[i]) 에 도달하면 이는 0으로, 인덱스가 음수에 도달하면 이는 len(grid[i])-1 로 치환해주어야 한다.
• 행(로우)은 처음과 끝의 이동이 불가능하다.  4번 판에서 1번 판의 비교는 당연히 할 수 없다.
• 어떤 인덱스의 전후좌우만 체크하는 게 아니라 인접한 수가 있으면 그 수의 전후좌우도 체크해 줘야 한다.

이 외에는 일반적으로 탐색하듯이 탐색하면 된다. 필자는 큐를 돌릴 때 인접한 수가 있는 경우에만 원본 좌표와 인접 좌표를 그리드에서 -1로 바꾸는 식으로 탐색했다.

 

3. 위 (2.)를 만족하는 경우가 하나라도 없으면 평균값을 구해서 연산을 실시한다.

 인접하는 숫자가 없어 지워지는 숫자가 하나라도 없을 경우 calcAvg()를 호출한다. 먼저 판의 평균값을 구한다. 이후 판에 남아있는 모든 숫자에 대해서 숫자 > 평균값이라면 숫자에 -1을, 숫자 < 평균값이라면 숫자에 +1을 해준다.

 

 이 로직에서 함정이 두 개 존재한다. (사실 꼼꼼하다면 함정도 아니다)

 

먼저, 평균값은 정수가 아닌 실수형이다. 문제를 꼼꼼히 보았다면 예시에서 이미 확인했겠지만, 다음을 한번 보자.

 

 

 왼쪽 판은 회전을 마친 판이고 오른쪽 판은 인접한 수가 없어 평균값 구해 연산을 해준 결과이다.

여기서 평균은 22/6 이므로 정수 값은 3이다. 한데 오른쪽 판을 보면 왼쪽 판의 첫 번째 판의 9시 부근에 있던 3이 4로 바뀐 것을 확인할 수 있다. (4는 3으로 바뀐 것도 확인할 수 있다.)

 

 문제에서는 그냥 평균값으로 주어져 있는 데다가, 예제를 꼼꼼히 보지 않고서는 습관적으로 정수로 형 변환을 하는 필자 같은 경우라면 이 함정에서 한번 넘어지게 된다.

 

 다음 함정은 다음과 같은 케이스이다.

# input>>
3 3 3
1 1 1
1 1 1
1 1 1
1 0 1
2 0 1
3 0 1

 70% 넘은 부분에서 런타임 에러를 겪었다면 위 테스트 케이스를 통과하지 못한 것이다.

 

 위 테스트 케이스는 세 번 원판을 돌리지만 초기 단계가 모두 1로 같은 숫자이다. 때문에 첫 번째 회전에서 판에 있는 모든 숫자가 지워지게 된다. 여기서 두 번째 회전에서는 더 이상 지워진 값이 없기 때문에 필자의 로직대로라면 평균값을 계산해야 한다. 필자는 평균값의 계산을 판 전체를 탐색하면서 숫자가 존재하는 경우 count를 +=1 해주고 숫자를 더해두었다가 그 더해진 숫자를 count로 나눠진 방식으로 구현했다.

 

 하지만 판에 아무런 숫자도 존재하지 않는데 평균을 계산하는 메소드에 들어오면 count는 0이 되어 대표적인 런타임 에러 '0으로 나눌 수 없습니다'를 겪게 되는 것이다. 필자는 count로 나누기 전 count가 0이면 리턴해주는 줄을 추가하여 통과하였다.

 

 

4. k 횟수만큼 이를 반복하다가 마지막에 남아있는 숫자의 총합을 출력한다.

 calcResult() 함수에서 그리드에 -1이 아닌 경우 숫자를 더해 반환해주며 이를 출력해준다.

 

 

한 번의 런타임 에러를 겪은 후 통과하였고, 시간 초과와 메모리 초과 또한 겪지 않았다.

 

 

---

 

[전체 소스코드]

def calcResult():
    global grid
    answer = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] != -1:
                answer += grid[i][j]  
    return answer

def calcTarget(x):
    global n
    resultList = []
    for i in range(1, n+1):
        if i % x == 0 : resultList.append(i-1)
    return resultList

def checkGrid(i,j):
    global grid
    result = 0
    directions = (1, 0), (-1, 0), (0, 1), (0, -1)
    qu = []
    qu.append([i,j])
    num = grid[i][j]
    while qu:
        nowx, nowy = qu.pop(0)        
        for dx, dy in directions:
            nextx = nowx + dx; nexty = nowy + dy;
            if nextx < 0 or nextx >= len(grid): continue
            if nexty == len(grid[i]): nexty = 0
            elif nexty < 0 : nexty = len(grid[0]) - 1
            if grid[nextx][nexty] == num:
                qu.append([nextx,nexty])
                grid[i][j] = -1
                grid[nextx][nexty] = -1
                result += 1
    return result
            
def calcAvg():
    global grid
    result = 0; count = 0;
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] != -1:
                result += grid[i][j]; count += 1
    if count == 0 : return
    result = result / count
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] != -1:
                if grid[i][j] > result: grid[i][j] -= 1
                elif grid[i][j] < result: grid[i][j] += 1

def rotate(targetList,d,k):
    global grid
    while k > 0:
        for target in targetList:
            if d == 1 : temp = grid[target][len(grid[target])-1]
            else: temp = grid[target][0]
            if d == 1 : 
                for j in range(len(grid[target])-1):
                    grid[target][len(grid[target])-1-j] = grid[target][len(grid[target])-1-j-1]
                grid[target][0] = temp
            else: 
                for j in range(len(grid[target])-1):
                    grid[target][j] = grid[target][j+1]
                grid[target][len(grid[target])-1] = temp
        k-=1
    result = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] != -1:
                result += checkGrid(i,j)
    if result == 0 : calcAvg()
         
def go(param):
    x,d,k = param
    targetList = calcTarget(x)
    rotate(targetList,1 if d == 0 else -1,k)
    
n, m, t = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
qu = []
for _ in range(t):
    qu.append(list(map(int,input().split())))
while qu:
    go(qu.pop(0))

print(calcResult())