백준(boj) 17822_원판 돌리기 (파이썬, c++)

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

풀이

---

인접한 곳에 같은 숫자이면 지워주고, 같은 숫자가 없는 경우에는 숫자들을 평균이랑 비교하여 1을 더하거나 빼주는 문제이다.

원판을 2차원 배열로 생각하면 크게 3가지 상황으로 나타낼 수 있다.

1.가로로 인접한 경우

2.세로로 인접한 경우

3.가로로 인접하나 처음과 끝으로 떨어져 있는 경우(원판이라서 나타나는 특징)

인접한 곳에 같은 숫자가 있는 경우 visit배열에 표시해놓고 전부 살펴본 후에 체크되어 있는 숫자들을 지워주었다. (가로, 세로 둘 다 같은 숫자인 경우 먼저 지우면 원하는 값을 못 구하므로 다 돌리고 처리) 1, 2 번은 4방향 위치 배열을 만들고 이 배열을 이용해 탐색하면서 체크해 주었고, 3번은 나머지 연산을 이용하였다.

python3

from sys import *
input = stdin.readline
from collections import *
​
def rotate(x, d, k):
    for i in range(x - 1, n, x):
        temp = []
        for j in range(m):
            if d == 1:  # 시계
                temp.append(a[i][(j + k) % m])
            elif d == 0:  # 반시계
                temp.append(a[i][(m + j - k) % m])
        a[i] = temp[:]
​
def bfs(x, y):
    q = deque()
    q.append((x, y))
    visit[x][y] = 1
    f = 0
    while q:
        x, y = q.popleft()
        for dx, dy in dd:
            nx, ny = x + dx, y + dy
            ny %= m                     #열의 처음, 끝 같은지도 확인해줘야 하므로 ny끝에 다다르면 %m 연산으로 처리
            if nx < 0 or ny < 0 or nx > n - 1 or ny > m - 1 or visit[nx][ny] or \
                    a[x][y] != a[nx][ny] or a[nx][ny] == 0: continue
            q.append((nx, ny))
            visit[nx][ny] = 1
            f = 1
    if f:
        return 1
    else:               #시작할때 visit 체크 해주는데, 같은게 없으면(f==0) 다시 0으로
        visit[x][y] = 0 
        return 0
​
def solve(x, d, k):
    flag = 0        #인접한 곳에 같은 숫자가 있으면 flag 활성화 시켜줌
    rotate(x, d, k)
    cnt, SUM = 0, 0
    for i in range(n):
        for j in range(m):
            if a[i][j]: cnt += 1
            SUM += a[i][j]
            if not visit[i][j] and a[i][j]:
                if bfs(i, j): flag = 1
    try:
        avg = SUM / cnt     #cnt 없는경우 => 모든 원소 0인 경우
    except:
        return              #종료
    for i in range(n):
        for j in range(m):
            if flag:        #같은게 있으면
                if visit[i][j]: a[i][j] = 0
            else:           #없으면
                if a[i][j] and a[i][j] > avg:
                    a[i][j] -= 1
                elif a[i][j] and a[i][j] < avg:
                    a[i][j] += 1
​
n, m, t = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
dd = [(-1, 0,), (1, 0), (0, -1), (0, 1)]
for i in range(t):
    x, d, k = map(int, input().split())
    visit = [[0] * m for _ in range(n)]
    solve(x, d, k)
ans = 0
for i in range(n):
    ans += sum(a[i])
print(ans)

c++

#include<iostream>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;
const int SIZE = 50;
int a[SIZE][SIZE];
int visit[SIZE][SIZE];
int n,m,t;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
typedef pair<int, int> P;
​
void rotate(int x, int d, int k){
    for(int i=x-1; i<n; i+=x){
        int temp[SIZE];
        for(int j=0; j<m; j++){
            if(d==1){
                temp[j] = a[i][(j+k)%m];
            }
            else if(d==0){
                temp[j] = a[i][(m+j-k)%m];
            }
        }
        for(int j=0; j<m; j++){
            a[i][j] = temp[j];
        }
    }
}
​
bool bfs(int x, int y){
    queue<P> q;
    q.push({x, y});
    visit[x][y]=1;
    bool f=0;
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx, ny;
            nx = x+dx[i];
            ny = y+dy[i];
            if (nx == x){                           //파이썬 C++ 음수 나머지 연산 다름, 따로처리
                if( ny == -1) ny = m - 1 ;
                else if (ny == m) ny = 0;
            }
            if(nx < 0 || ny < 0 || nx > n-1 || ny > m-1 || visit[nx][ny] || a[x][y]!=a[nx][ny] || a[nx][ny]==0) continue;
            q.push({nx, ny});
            visit[nx][ny] = 1;
            f=1;
        }
    }
    if(!f) visit[x][y]=0;
    return f;
}
​
void solve(int x, int d, int k){
    bool flag = 0;
    rotate(x, d, k);
    double SUM=0;
    int cnt=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(a[i][j]) cnt+=1;
            SUM+=a[i][j];
            if(!visit[i][j] && a[i][j]){
                if(bfs(i, j)){
                    flag=1;
                }
            }
        }
    }
    if(cnt == 0) return;
    double avg = SUM / cnt;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(flag){
                if(visit[i][j]) a[i][j]=0;
            }
            else{
                if(a[i][j] && a[i][j] > avg) a[i][j]-=1;
                else if(a[i][j] && a[i][j] < avg) a[i][j]+=1;
            }
        }
    }
}
int main()
{
    scanf("%d %d %d", &n, &m, &t);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d", &a[i][j]);
    for(int i=0; i<t; i++){
        int x,d,k;
        scanf("%d %d %d", &x, &d, &k);
        memset(visit, 0, sizeof(visit));
        solve(x, d, k);
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            ans += a[i][j];
        }
    }
    printf("%d", ans);
    return 0;
}

고찰

---

python코드를 C++로 옮기는 과정에서 두 언어의 음수를 나머지 연산한 결과가 달라 많이 헤맸었다. 나머지 연산을 할 때 음수가 있으면 주의해야 겠다.

http://agile.egloos.com/1666312 << 음수의 나머지 연산은 이 글 뒤쪽의 p.s만 보면 이해가 쉽게 될 듯 하다.