백준 1012 - 유기농 배추

문제

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

1012번: 유기농 배추

끊어지지 않고 이어져있는 그래프의 수가 몇개 인지 찾는 문제이다. 즉 컴포넌트의 개수를 찾으면 된다.

 

풀이

입력받은 배추의 위치를 2차원 배열에 저장한다. 2차원 배열의 크기만큼 돌면서 1인 인덱스에서 상하좌우 방향에 1이 있는지 재귀적으로 검사한다. 검사한 곳은 0으로 바꾼다. 가장자리 부분에서도 똑같이 검사 할 수 있도록 2차원 배열의 크기를 2만큼 늘려서 가상의 가장자리를 만들어줘서 풀 수 있다

 

1. N * M 2차원 배열을 하나씩 접근해서 값이 1인지 검사한다.

2. 1이면 지렁이 수를 증가하고 그 인덱스 값을 0으로 바꾼다.

3. 상하좌우를 검사해서 1이면 0으로 바꾸고 그 자리에서 상하좌우를 검사한다.

 

코드

c++

#include <iostream>
 
using namespace std;
 
int board[52][52];
 
void dfs(int row, int col)
{
    if (board[row - 1][col] == 1)
    {
        board[row - 1][col] = 0;
        dfs(row - 1, col);
    }
 
    if (board[row + 1][col] == 1)
    {
        board[row + 1][col] = 0;
        dfs(row + 1, col);
    }
 
    if (board[row][col - 1] == 1)
    {
        board[row][col - 1] = 0;
        dfs(row, col - 1);
    }
 
    if (board[row][col + 1] == 1)
    {
        board[row][col + 1] = 0;
        dfs(row, col + 1);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int T;
    cin >> T;
 
    for (int i = 0; i < T; i++)
    {
        int result = 0;
 
        // 판 초기화
        for (int x = 1; x <= 50; x++)
        {
            for (int y = 1; y <= 50; y++)
            {
                board[x][y] = 0;
            }
        }
 
        // 배추 위치 입력
        int M, N, K;
        cin >> M >> N >> K;
        for (int j = 1; j <= K; j++)
        {
            int x, y;
            cin >> y >> x;
            board[x + 1][y + 1] = 1;
        }
 
        // 컴포넌트의 수 검사
        for (int x = 1; x <= N; x++)
        {
            for (int y = 1; y <= M; y++)
            {
                if (board[x][y] == 1)
                {
                    result++;
                    board[x][y] = 0;
                    dfs(x, y);
                }
            }
        }
 
        cout << result << '\n';
    }
 
    return 0;
}
 

 

파이썬

import sys 
sys.setrecursionlimit(10000)
 
def dfs(i, j, graph, n, m):
    graph[i][j] = 0
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for d in dirs:
        nx = i + d[0]
        ny = j + d[1]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
 
        if graph[nx][ny] == 1:
            dfs(nx, ny, graph, n, m)
 
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0]*m for i in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1
 
    result = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(i, j, graph, n, m)
                result += 1
    print(result)