BOJ_1012 유기농 배추

TOC {:toc}

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

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

2021.07.03 (Python)

메모리	시간	코드 길이
29200 KB	84 ms	760 B

단계	시작 시각	끝난 시각
문제 이해	16:16:42	16:18:56
풀이 생각	16:20:10	16:24:02
코딩	21:15:55	21:32:14
디버깅	21:34:44	21:38:06

import sys
input = sys.stdin.readline

def dfs(x, y):
    global cab
    cab[x][y] = False
    stack = [(x, y)]

    while stack:
        i, j = stack.pop()
        for c in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            cx, cy = c
            if 0 <= cx < M and 0 <= cy < N and cab[cx][cy]:
                cab[cx][cy] = False
                stack.append(c)


for _ in range(int(input())):
    M, N, K = map(int, input().split())
    cab = [[False] * N for _ in range(M)]
    count = 0

    for _ in range(K):
        X, Y = map(int, input().split())
        cab[X][Y] = True
    
    for i in range(M):
        for j in range(N):
            if cab[i][j]:
                dfs(i, j)
                count += 1
    
    print(count)

아이디어 & 풀이

일반적으로 노드의 수에 따라 1차원으로 구현하던 visited를 2차원으로 확장한 뒤 dfs나 bfs로 인접한 배추들을 탐색한다.

크기 M x N의 이차원 리스트 cab을 만든 뒤 입력받은 배추의 위치만 True로 바꾼다.
cab을 완전 탐색하면서 해당 위치에 배추가 있으면 (i.e., 값이 True 이면) 그 값을 False로 바꾸고 dfs나 bfs를 이용해 모든 근접한 배추들을 탐색하면서 값을 False로 바꾼다.
- (i, j)의 배추에 인접한 배추들의 위치: (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)
인접한 배추를 모두 탐색한 뒤 count를 1 증가시킨다.

다시 이차원 리스트를 이어서 탐색하며 위 과정을 반복한 뒤 탐색이 끝나면 count를 출력한다.

디버그

모서리에 위치한 배추들은 인접한 위치 (e.g., (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))가 리스트 범위 밖일 수 있다.
- cab[cx][cy]를 확인할 때 cx, cy가 범위 안의 수인지도 같이 확인한다.

2022.04.05 (JS)

메모리	시간	코드 길이
12572 KB	208 ms	1283 B

단계	시작 시각	끝난 시각
문제 이해	23:23:39	23:27:12
풀이 생각	23:45:43	23:46:58
코딩	23:47:00	00:17:15

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

function bfs(field, i, j, M, N) {
    const dx = [1, 0, -1, 0];
    const dy = [0, -1, 0, 1];

    const queue = [[i, j]];
    field[j][i] = 0;

    while (queue.length) {
        const [x, y] = queue.shift();

        for (let i = 0; i < 4; i += 1) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (0 <= nx && nx < M && 0 <= ny && ny < N && field[ny][nx]) {
                field[ny][nx] = 0;
                queue.push([nx, ny]);
            }
        }
    }
}

function main(field, M, N) {
    let count = 0;

    for (let j = 0; j < N; j += 1) {
        for (let i = 0; i < M; i += 1) {
            if (field[j][i]) {
                bfs(field, i, j, M, N);
                count += 1;
            }
        }
    }
    return count;
}

const [T, ...lines] = input;
let j = 0;

for (let i = 0; i < T; i += 1) {
    const [M, N, K] = lines[j].split(" ").map((n) => parseInt(n));
    let field = Array.from(Array(N), () => Array(M).fill(0));

    for (let k = 1; k < K + 1; k += 1) {
        const [x, y] = lines[j + k].split(" ").map((n) => parseInt(n));
        field[y][x] = 1;
    }

    console.log(main(field, M, N));

    j += K + 1;
}

피드백

순서 신경(reverse) 안써도 되면 dfs가 더 빠르니까 dfs를 사용하는 게 나을 것 같다.
이번 문제는 크게 차이는 안 나는 것 같다.

참고 답안

# 풀이 1-1
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    fields = {}
    for _ in range(int(input().split()[2])):
        fields[tuple(map(int, input().split()))] = None

    count = 0
    while fields:
        count += 1
        stack = [fields.popitem()[0]]
        while stack:
            x, y = stack.pop()
            for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                adj = (x + i, y + j)
                if adj in fields:
                    del fields[adj]
                    stack.append(adj)
    print(count)

# 풀이 1-2
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def dfs(i, j):
    global maps

    if maps[i][j] == 1:
        maps[i][j] = 0
        if i + 1 < N and maps[i + 1][j] == 1:
            dfs(i + 1, j)
        if 0 <= i - 1 and maps[i - 1][j] == 1:
            dfs(i - 1, j)
        if j + 1 < M and maps[i][j + 1] == 1:
            dfs(i, j + 1)
        if 0 <= j - 1 and maps[i][j - 1] == 1:
            dfs(i, j - 1)


for T in range(int(input())):
    N, M, K = map(int, input().split())
    maps = [[0] * M for _ in range(N)]

    for _ in range(K):
        i, j = map(int, input().split())
        maps[i][j] = 1
    cnt = 0

    for i in range(N):
        for j in range(M):
            if maps[i][j] == 1:
                dfs(i, j)
                cnt += 1
    print(cnt)

아이디어 & 풀이

풀이 1-1: 이차원 리스트 대신 딕셔너리를 사용했다.
풀이 1-2: dfs를 구현을 다르게 했다. 인접한 배추의 위치를 각각의 조건으로 작성하고 재귀를 사용해서 구현한다.