[BOJ] 16768. Mooyo Mooyo.py(Blood Field)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 같은 색상이면 0으로 변경

- 하강하여 0으로 된 결과 셀을 채울 수 있음

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

뿌요뿌요 게임과 같은 동작이다.

K 개만큼 같은 색상이 모이면 터지게 된다.

입력이 아래와 같다면

6 3

0000000000

0000000300

0054000300

1054502230

2211122220

1111111223

K = 3으로 연결된 색상을 모두 0으로 변경할 수 있다.

0000000000

0000000300

0054000300

1054502230

2211122220

1111111223

0으로 변경하면 아래와 같다.

0000000000

0000000300

0054000300

1054500030

2200000000

0000000003

중력이 적용되면 0으로 된 결과셀을 채울 수 있다고 하였으니,

아래과 같이 떨어지게 된다.

0000000000

0000000000

0000000000

0000000000

1054000300

2254500333

여기서도 K = 3, 을 적용하면

0000000000

0000000000

0000000000

0000000000

1054000300

2254500333

0으로 변경하면 

0000000000

0000000000

0000000000

0000000000

1054000000

2254500000

여기서 더이상 K = 3 을 만족하는 색상이 없으므로 출력해주면 된다.

정리해보면,

1. 상하좌우를 탐색하면서 같은 색상인 경우 방문하면서 ck[][]에 check

2. 탐색을 완료했을 때, 같은 색상이 K보다 크거나 같은 경우 ck[][]에 check되어있는 좌표에 해당하는 Map[][]을 0으로 수정

3. N-1번째 줄부터 아래 좌표가 0일 경우 내려줌

#. Python Code

dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
N, K = map(int, input().split())
grd = [list(input()) for _ in range(N)]
ck, ck2 = [], []
 
def reset():
    return [[0 for j in range(10)] for i in range(N)]
 
def DFS(x, y):
    global grd, ck
    ck[x][y] = 1
    cnt = 1
 
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:
            continue
        if ck[xx][yy] or grd[xx][yy] != grd[x][y]:
            continue
        cnt += DFS(xx, yy)
 
    return cnt
 
def DFSZ(x, y, clr):
    global grd, ck2
    ck2[x][y] = 1
    grd[x][y] = '0'
 
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:
            continue
        if ck2[xx][yy] or grd[xx][yy] != clr:
            continue
        DFSZ(xx, yy, clr)
 
def Down():
    global grd
    while True:
        exist = False
 
        for x in range(N-2, -1, -1):
            for y in range(10):
                if grd[x][y] != '0' and grd[x+1][y] == '0':
                    grd[x + 1][y], grd[x][y] = grd[x][y], '0'
                    exist = True
 
        if not exist:
            break
 
while True:
    exist = False
    ck, ck2 = reset(), reset()
 
    for x in range(N):
        for y in range(10):
            if grd[x][y] != '0' and not ck[x][y]:
                cnt = DFS(x, y) # 탐색
                if cnt >= K:
                    exist = True
                    DFSZ(x, y, grd[x][y]) # 0으로 수정
 
    if not exist:
        break
    Down() # 하강
 
for i in grd:
    print(''.join(i))

흐아.. 어째 꾸역꾸역 풀긴 했는데 정리좀 해보자..

// main

line 51~65) 더이상 할 작업이 없을 때까지 반복

line 55~61) 모든 좌표를 탐색

line 57) 해당 좌표가 0이 아니고, 방문하지 않은 곳이라면

line 58) 해당 좌표의 색상과 같은 색상이 주변에 몇 개가 있는지 확인하는 DFS() 함수 호출

line 59) 주변에 같은 색상이 K개 이상 있을 경우

line 60) 변경사항이 생겼다는 check

line 61) 주변에 같은 색이 K개 이상 모인 그룹을 모두 0으로 수정

line 63) 변경사항이 생기지 않았을 경우 반복문 종료

line 65) 변경사항이 생겼을 경우 하강 동작을 수행하는 Down() 함수 호출

line 67) 최종 결과 출력

// 함수

line 6) check[][]을 reset 해주는 함수

line 9~22) 해당 좌표의 색상과 같은 색상이 주변에 몇 개가 있는지 return

line 11) 해당 좌표를 방문했다고 check

line 12) 현재 같은 색이 1개이므로 cnt는 1로 초기화

line 14~20) 상하좌우에 같은 색상이 있나 탐색

line 15) 다음 좌표를 저장

line 16) 좌표 영역을 벗어날 경우 continue

line 18) 이미 방문했거나 색상이 다를 경우 continue

line 20) 지금 좌표로부터 주변 좌표에 같은 색상이 몇 개 있는지 cnt에 누적

line 22) 최종적으로 초기 좌표로부터 같은 색상으로 연결된 좌표의 개수를 return

line 24~35) 주변에 같은 색이 K개 이상 모인 그룹을 모두 0으로 수정해주는 함수

line 26) 0으로 수정하는 과정에서도 check배열이 필요(다른 좌표에 있는데 색이 같을 경우 발생하는 문제를 해결하기 위함)

line 27) 그룹 내 좌표들을 방문하며 '0'으로 수정

line 29~35) 상하좌우에 같은 색상이 있나 탐색

line 30) 다음 좌표를 저장

line 31) 좌표 영역을 벗어날 경우 continue

line 33) 이미 '0'으로 변경했거나 색상이 다를 경우 continue

line 35) 같은 색으로 연결된 다음 좌표도 '0'으로 수정해주기 위해 재귀함수 호출

line 37~49) 변경사항이 생겼을 경우 하강 동작을 수행하는 Down() 함수

line 39) 모두 하강이 완료할 때까지 반복

line 42~46) N-2 지점부터 하단에 '0'이 있는지 확인

line 44) 해당 좌표가 '0'이 아닌데 하단에 '0'이 있을 경우

line 45) 해당 색상을 하강

line 46) 변경사항 check

line 48) 변경사항이 생기지 않았다면 반복문 종료

#. Python Other Code

def new_array(N):
    return [[False for i in range(10)] for _ in range(N)]
 
 
N, K = map(int, input().split())
M = [list(input()) for _ in range(N)]
ck = new_array(N)
ck2 = new_array(N)
 
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
 
 
def dfs(x, y):
    ck[x][y] = True
    ret = 1
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:
            continue
        if ck[xx][yy] or M[x][y] != M[xx][yy]:
            continue
        ret += dfs(xx, yy)
    return ret
 
 
def dfs2(x, y, val):
    ck2[x][y] = True
    M[x][y] = '0'
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:
            continue
        if ck2[xx][yy] or M[xx][yy] != val:
            continue
        dfs2(xx, yy, val)
 
 
def down():
    for i in range(10):
        tmp = []
        for j in range(N):
            if M[j][i] != '0':
                tmp.append(M[j][i])
        for j in range(N-len(tmp)):
            M[j][i] = '0'
        for j in range(N-len(tmp), N):
            M[j][i] = tmp[j - (N-len(tmp))]
 
 
while True:
    exist = False
    ck = new_array(N)
    ck2 = new_array(N)
    for i in range(N):
        for j in range(10):
            if M[i][j] == '0' or ck[i][j]:
                continue
            res = dfs(i, j)  # 개수 세기
            if res >= K:
                dfs2(i, j, M[i][j])  # 지우기
                exist = True
    if not exist:
        break
    down()  # 내리기
 
 
for i in M:
    print(''.join(i))

하강해주는 함수의 동작이 살짝 다른데

line 38~47) 하강 동작 함수

line 39) 세로 방향으로 반복

line 42) 해당 세로 라인에 '0'이 아닌 숫자들을 lst에 저장

line 44~45) '0'이 아닌 숫자를 채울 공간을 제외하고 '0'으로 수정

line 46~47) '0'이 아닌 숫자를 하단에 쌓아줌

생각보다 복잡했다.. 그래도 풀다보니 이해는 가서 다행이다ㅠㅠ

C++로도 다시 풀어봐야겠다.

#. C++ Code

#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
int N, K, map[100][100];
bool ck[100][100], ck2[100][100];
 
int DFS(int x, int y)
{
    int cnt = 1;
    ck[x][y] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx < 0 || xx >= N || yy < 0 || yy >= 10) continue;
        if (ck[xx][yy] || map[xx][yy] != map[x][y]) continue;
 
        cnt += DFS(xx, yy);
    }
 
    return cnt;
}
 
void DFSZ(int x, int y, int colr)
{
    ck2[x][y] = true;
    map[x][y] = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx < 0 || xx >= N || yy < 0 || yy >= 10) continue;
        if (ck2[xx][yy] || map[xx][yy] != colr) continue;
 
        DFSZ(xx, yy, colr);
    }
}
 
void Down()
{
    int i, j;
 
    for (i = 0; i < 10; i++)
    {
        vector<int> vt;
 
        for (j = 0; j < N; j++)
        {
            if (map[j][i])
                vt.push_back(map[j][i]);
        }
 
        for (j = 0; j < N - vt.size(); j++)
            map[j][i] = 0;
 
        for (j = N - vt.size(); j < N; j++)
            map[j][i] = vt[j - (N - vt.size())];
    }
}
 
int main(void)
{
    int i, j;
    bool changed;
    //freopen("input.txt", "rt", stdin);
    scanf("%d %d", &N, &K);
    for (i = 0; i < N; i++)
        for (j = 0; j < 10; j++)
            scanf("%1d\n", &map[i][j]);
 
    while (true)
    {
        changed = false;
        memset(ck, false, sizeof(ck));
        memset(ck2, false, sizeof(ck2));
 
        for (i = 0; i < N; i++)
        {
            for (j = 0; j < 10; j++)
            {
                if (!map[i][j] || ck[i][j]) continue;
                int cnt = DFS(i, j); // Find
 
                if (cnt >= K)
                {
                    changed = true;
                    DFSZ(i, j, map[i][j]);    // Delete
                }
            }
        }
 
        if (!changed)
            break;
 
        Down();    // Down
    }
 
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < 10; j++)
            printf("%d", map[i][j]);
 
        puts("");
    }
 
    return 0;
}