BOJ_16768 Mooyo Mooyo

TOC {:toc}

이 글은 백준 온라인 저지의 16768번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.08.16 (Python)

메모리	시간	코드 길이
29200 KB	92 ms	1427 B

단계	시작 시각	끝난 시각
문제 이해 1	16:20:15	16:25:34
풀이 생각 1-1	16:28:53	16:32:47
풀이 생각 1-2	11:37:48	12:30:32
코딩 1-1	12:30:34	13:05:15
코딩 1-2	14:38:51	15:56:08
풀이 생각 2-1	16:08:33	16:42:16
코딩 2-1	20:43:49	21:32:00
풀이 생각 2-2	21:35:48	21:49:02
코딩 2-2	21:49:13	22:48:18
코딩 2-3	23:44:42	00:47:15
디버깅(강의 후)	11:48:13	12:28:10

N, K = map(int, input().split())
board = [list(input()) for _ in range(N)][::-1]
visited = [[False] * 10 for _ in range(N)]

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

# 깊이 우선 탐색으로
# 서로 인접해있는 n들의 좌표를 구하는 함수
def dfs(x, y, n):
    global visited

    visited[x][y] = True
    stack = [(x, y)]
    tmp = []

    while stack:
        x, y = stack.pop()
        tmp.append((x, y))

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= 10:
                continue
            if not visited[nx][ny] and board[nx][ny] == n:
                visited[nx][ny] = True
                stack.append((nx, ny))
    return tmp


# 이번 스텝에서 제거될 haybale(pop)을 구하는 함수
def search_pop():
    P = set([])

    for i in range(N):
        for j in range(10):
            if board[i][j] != "0" and not visited[i][j]:
                tmp = dfs(i, j, board[i][j])
                if len(tmp) >= K:
                    P.update(tmp)
    return P


# 0으로 변한 부분에 위의 haybale을 끌어 내려오는 함수
def down():
    for j in range(10):
        tmp = []
        for i in range(N):
            if board[i][j] != "0":
                tmp.append(board[i][j])
        for i in range(len(tmp)):
            board[i][j] = tmp[i]
        for i in range(len(tmp), N):
            board[i][j] = "0"


# 제거되는 게(P) 없을 때까지 진행을 반복한다.
while True:
    visited = [[False] * 10 for _ in range(N)]
    P = search_pop()

    if not P:
        for row in board[::-1]:
            print("".join(row))
        break

    for i, j in P:
        board[i][j] = "0"
    down()

아이디어 & 풀이

N, K와 haybale의 맵인 board를 입력값을 받는다.

board를 받을 때 이후 haybale을 아래로 끌어 내리는 과정을 쉽게 하기 위해 열을 역순으로 받는다.

while문으로 다음의 과정을 반복하면서 조건에 따라 board를 수정한다.

board가 바뀌었으므로 visited를 초기화한다.
search_pop으로 제거할 haybale 좌표 리스트인 P를 받아온다.
P에 원소가 없는 경우 출력하고 실행을 종료한다.
- board의 열을 역순으로 받았기 때문에 역순으로 출력한다.
P의 원소 좌표에 해당하는 값을 모두 "0"으로 바꾼 뒤
down 함수로 위의 haybale들을 끌어 내린다.

search_pop 함수는 다음과 같이 구현한다.

board를 완전 탐색하면서 해당 값이 "0"이 아니거나 방문한 적이 없는 경우에만 다음의 과정을 반복한다.
해당 좌표(x, y)와 값(n)을 인자로 dfs 함수를 실행한다.
dfs는 x, y와 인접해있는 n 값들의 좌표 리스트를 반환한다.
dfs의 반환 리스트의 길이가 K보다 크거나 같으면 집합 P에 업데이트한다.

down 함수는 다음과 같이 구현한다.

하나의 열을 순회하면서 "0"이 아닌 원소를 tmp에 담는다.
tmp의 원소를 board 가장 아래부터 채우고 나머지는 "0"으로 채운다.
위에서 열을 역순으로 받았기 때문에 인덱스 0부터 시작하면 된다.

디버그

down 함수를 잘못 구현했었다.
- 아래서부터 한 칸씩 올라가면서 "0"이 아닌 원소가 나오면 break하고 그 값의 인덱스인 i를 받아왔다. 이 값을 이용해 일대일 대응으로 가장 아래에 i번째 값을 대입한 뒤 남은 부분을 0으로 채웠다.
- 이렇게 하면 0이 아닌 수 사이에 0이 끼어있을 경우 그사이의 0도 유지된 채 끌어내려진다.

피드백

코딩 2-1 과정까지 문제를 아예 잘못 이해하고 있었다.
- 문제 조건은 방향에 상관없이 상하좌우로 인접해있기만 하면 제거되는 것이었는데
- 가로나 세로 일렬로 연속되어 있어야 제거되는 것으로 이해하고 해결하고 있었다.
- 문제를 제대로 읽고 예제 입력에 따라 예제 출력을 도출하는 과정을 꼼꼼히 시뮬레이션해야겠다.
입/출력을 모두 문자열로 해야 하고 board의 값으로 계산을 하거나 하지 않기 때문에 int로 변환하지 않는 게 더 낫다.
- 0인지 아닌지 판단하는 조건을 쓸 때 주의해야 한다.
- 원소가 문자이므로 "0"과 비교해야 하고, not A와 같은 방식으로 0을 판단하면 안 된다.

값이 "0"인 원소를 거르는 것을 dfs 안에서 했는데 search_pop 안에서 하는 게 더 깔끔한 것 같다.

# dfs 안에서 "0"인 원소를 거르는 경우

# def dfs
if not visited[nx][ny]:
    if board[nx][ny] != "0":
        visited[nx][ny] = True
        continue
    if board[nx][ny] == n:
        visited[nx][ny] = True
        stack.append((nx, ny))

# def search_pop
if not visited[i][j] != 0:
    tmp = dfs(i, j, board[i][j])

위의 답안은 수정한 상태이다.

2022.04.09 (JS)

메모리	시간	코드 길이
14844 KB	340 ms	2077 B

단계	시작 시각	끝난 시각
문제 이해	11:11:34	11:15:32
풀이 생각	11:15:36	11:22:59
코딩	11:23:07	12:10:24

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function dfs(x, y, n) {
    const visited = Array(N)
        .fill()
        .map((i) => Array(10).fill(false));
    visited[y][x] = true;

    const stack = [[x, y]];
    const chunk = [[x, y]];
    const dx = [1, 0, -1, 0];
    const dy = [0, -1, 0, 1];

    while (stack.length) {
        const [x, y] = stack.pop();
        for (let i = 0; i < 4; i += 1) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (0 <= nx && nx < 10 && 0 <= ny && ny < N && muyo[ny][nx] === n && !visited[ny][nx]) {
                visited[ny][nx] = true;
                stack.push([nx, ny]);
                chunk.push([nx, ny]);
            }
        }
    }

    return chunk;
}

function pop(chunk) {
    chunk.forEach((coord) => {
        const [x, y] = coord;
        muyo[y][x] = "0";
    });
}

function fall() {
    for (let i = 0; i < 10; i += 1) {
        const col = [];
        for (let j = 0; j < N; j += 1) {
            col.push(muyo[j][i]);
        }
        const left = col.filter((elem) => elem !== "0");
        const newCol = Array(N - left.length).fill("0");
        newCol.push(...left);
        for (let j = 0; j < N; j += 1) {
            muyo[j][i] = newCol[j];
        }
    }
}

function main() {
    let isChanged = true;
    while (isChanged) {
        isChanged = false;
        for (let j = 0; j < N; j += 1) {
            for (let i = 0; i < 10; i += 1) {
                if (muyo[j][i] !== "0") {
                    const chunk = dfs(i, j, muyo[j][i]);
                    if (chunk.length >= K) {
                        pop(chunk);
                        isChanged = true;
                    }
                }
            }
        }
        fall();
    }
    console.log(muyo.map((line) => line.join("")).join("\n"));
}

const [NK, ...lines] = input;
const [N, K] = NK.split(" ").map((n) => parseInt(n));
const muyo = lines.map((line) => line.split("")); // cell is char

main();

아이디어 & 풀이

임시 작성

cell들을 순회하면서
- 0이 아닌 원소는 dfs로 진입
- 순회하면서 출발점과 같으면 좌표를 stack에 push, chunk에도 push
- 더 push할 게 없을 때 chunk의 length를 세서 K 이상이면
- 해당 좌표를 순회하면서 0으로 바꿈
- 반복
세로를 순회하면서 원소를 다 모은 뒤 0을 필터링하고 K개가 되도록 원소를 다시 채운 뒤 열을 교체

피드백

함수 매개변수 수정헀을 때 정확히 확인하고 제대로 전달하자.
push의 반환값은 push 이후 배열의 원소의 개수라는 것을 기억하자. 반환 값이 변경된 배열이 아닌 메소드들을 주의하기.

참고 답안

def new_array(N):
    return [[False] * 10 for _ in range(N)]


N, K = map(int, input().split())
M = [list(input()) for _ in range(N)]
visited = new_array(N)
visited2 = new_array(N)

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]


# 연속된 원소의 개수를 세는 함수
def dfs(x, y):
    visited[x][y] = True
    ret = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= N or ny < 0 or ny >= 10:
            continue
        if visited[nx][ny] or M[x][y] != M[nx][ny]:
            continue
        ret += dfs(nx, ny)
    return ret


# 원소가 K가 넘었을 때 삭제하는 함수
def dfs2(x, y, val):
    visited2[x][y] = True
    M[x][y] = "0"
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= N or ny < 0 or ny >= 10:
            continue
        if visited2[nx][ny] or M[nx][ny] != val:
            continue
        dfs2(nx, ny, val)


# 아래로 내리는 함수
def down():
    for j in range(10):
        tmp = []
        for i in range(N):
            if M[i][j] != "0":
                tmp.append(M[i][j])
        for i in range(N - len(tmp)):
            M[i][j] = "0"
        for i in range(N - len(tmp), N):
            M[i][j] = tmp[i - (N - len(tmp))]


# 변화가 없을 때까지 위 과정을 반복한다.
while True:
    exist = False
    visited = new_array(N)
    visited2 = new_array(N)
    for i in range(N):
        for j in range(10):
            if M[i][j] == "0" or visited[i][j]:
                continue
            res = dfs(i, j)
            if res >= K:
                dfs2(i, j, M[i][j])
                exist = True
    if not exist:
        break
    down()

for row in M:
    print("".join(row))

아이디어 & 풀이

전체적인 진행은 위의 풀이와 유사하다. 다음과 같은 차이점이 있다.

더는 변화가 없는 경우를 파악하기 위해서 exist 변수를 boolean으로 관리한다.
- 제거할 게 있는 경우만 True로 값을 바꾸고, 값이 False일 경우 break 한다.
인접한 같은 수의 ‘개수’를 파악하는 dfs와 인접한 같은 수를 제거하는 (0으로 바꾸는) dfs2를 따로 관리한다.
- visited 리스트도 visited와 visited2 두 개로 관리한다.