[Python] 백준_원판 돌리기(17822)

문제

 

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

 

풀이

 

원판을 반시계방향으로 회전하는 것은 배열의 맨 앞 원소를 맨 뒤에 보내면되고, 시계방향으로 회전하는 것은 맨 뒤의 원소를 맨 앞에 보내면됨.

 

원판을 회전시킨 이후에 인접한 원소를 확인해야하므로 DFS를 이용하였음.

check 메서드에서 temp변수는 원판에서 지워진 원소가 있는지 확인하는 변수고, temp_check는 0이 아닌 원소를 시작으로 인접한 원소들을 확인할때 인접한 원소가 있는지를 확인하는 변수임.

만약 0이 아닌 원소를 미리 바꿔두고 DFS를 진행하면 인접한 원소가 없을 때 다시 기존값으로 바꿔줘야하기때문에 temp_check를 이용하였음.

 

인접한 원소가 없는 경우에는 평균을 계산해서 각 원소에 1을 더하거나 빼야하는데, 0으로 나누지않도록 주의해야함.

n,m,t = map(int,input().split())
board = []
ad = [(0,1),(0,-1),(1,0),(-1,0)]
def rotate(i,d,k):
    global board
    if d == 0:
        for _ in range(k):
            board[i] = [board[i][-1]] + board[i][:m - 1]
    else:
        for _ in range(k):
            board[i] = board[i][1:] + [board[i][0]]
def check():
    global board
    temp = False
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                num = board[i][j]
                temp_check = False
                queue = [(i,j)]
                while queue:
                    cur = queue.pop()
                    for k in range(4):
                        nx = cur[0] + ad[k][0]
                        ny = cur[1] + ad[k][1]
                        if nx < 0 or nx >= n:
                            continue
                        if ny < 0:
                            ny += m
                        if ny >= m:
                            ny -= m
                        if board[nx][ny] == num:
                            queue.append((nx,ny))
                            temp = True
                            temp_check = True
                            board[nx][ny] = 0
                if temp_check:
                    board[i][j] = 0
    if temp:
        return
    avg = 0
    count = 0
    for i in range(n):
        for j in range(m):
            avg += board[i][j]
            if board[i][j] != 0:
                count += 1
    if count == 0:
        return
    avg /= count
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                if board[i][j] > avg:
                    board[i][j] -= 1
                elif board[i][j] < avg:
                    board[i][j] += 1
for _ in range(n):
    board.append(list(map(int,input().split())))
for _ in range(t):
    x,d,k = map(int,input().split())
    for i in range(n):
        if (i + 1) % x == 0:
            rotate(i,d,k)
    check()
result = 0
for i in range(n):
    for j in range(m):
        result += board[i][j]
print(result)

 

 

_____________________________________________________________________________________________________

 

원판이 독립적이라길래 각 원판별로 지워진 원소가 없으면 평균을 구해서 더하거나 빼는 건줄 알았는데 아니었음. 문제를 잘못이해하는 경우가 너무많음..제대로 읽기