백준 1012: 유기농 배추 [C++]

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

 

 

가로길이 3, 세로길이 2인 표가 있다고 치자.

아보카도	고래	가오리
소방차	고슴도치	송전탑

일반적으로 좌표 표기는 (행, 열)로 한다. 고래의 좌표는 0행 1열이므로 (0, 1) 처럼 표기할 수 있다.

행과 열의 뜻이 그러하듯 0은 세로길이 기준이고 1은 가로길이 기준이다.

송전탑의 좌표 역시 1행 2열이므로 (1, 2)이다. 순서대로 세로길이, 가로길이 기준이다.

그러니까 가로길이 M, 세로길이 N을 주고 좌표를 x(m 기준), y(n 기준) 으로 줬다면 표기할 때는 둘을 뒤집어서 board[y][x] = 1과 같이 표기해줘야 하는 것이다.

 

상하좌우로 이웃한 배추들은 하나로 쳐도 된다.

주어진 보드에서 상하좌우 이웃한 배추들의 덩어리가 몇 갠지 세는 문제.

비슷한 문제를 푼 적이 있어서 DFS임은 바로 알 수 있었다. 근데 저놈의 행렬이 나를

 

DFS는 순환호출로 구현한다. 이를 위해서는 방문 여부를 기록할 배열 visited가 필요하다.

좌표를 입력받아 해당좌표에 방문 표시를 하고, 상하좌우 방향으로 계속 깊이우선탐색을 해나간다. 종료 조건은 다음 좌표가 보드를 벗어나거나, 배추가 없거나, 이미 방문한 정점일 때이다.

그렇지 않을 때는 계속해서 dfs를 호출해 탐색해나간다.

void dfs(int x, int y, int m, int n) {
    visited[y][x] = true;

    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx >= 0 && tx < m && ty >= 0 && ty < n && board[ty][tx] == 1 && !visited[ty][tx]) {
            dfs(tx, ty, m, n);
        }
    }
}

 

전체 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0}; // 상하좌우

int board[51][51];
bool visited[51][51];

void dfs(int x, int y, int m, int n) {
    visited[y][x] = true;

    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx >= 0 && tx < m && ty >= 0 && ty < n && board[ty][tx] == 1 && !visited[ty][tx]) {
            dfs(tx, ty, m, n);
        }
    }
}

int main() {
    int t, m, n, k, x, y;
    cin >> t;
    while (t--) {
        cin >> m >> n >> k;
        memset(board, 0, sizeof(board));
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            board[y][x] = 1; // 가로길이가 열임에 주의
        }
        int answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[j][i] == 1 && !visited[j][i]) { //배추가 있고, 아직 방문하지 않았을 때
                    dfs(i, j, m, n); //dfs 수행
                    answer++; //dfs가 종료되었다면 배추모임덩어리(한마리로 커버가능한) 하나를 탐색완료한 것이므로 answer 증가
                }
            }
        }
        cout << answer << '\n';
    }

    return 0;
}

 

서치하다가 dfs는 dfs인데, visited 배열을 따로 쓰지 않고 상하좌우 인접한 배추를 방문하면 보드의 해당 칸을 0으로 만드는 식으로 구현한 코드를 볼 수 있었다. 그것도 좋은 듯