๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/BOJ

[C++/BOJ] 1012 : ์œ ๊ธฐ๋† ๋ฐฐ์ถ” (BFS/DFS)

728x90

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

๋ฌธ์ œ

์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ”๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„ ๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  ์žˆ์œผ๋ฉด ์ด ์ง€๋ ์ด๋Š” ์ธ์ ‘ํ•œ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด, ๊ทธ ๋ฐฐ์ถ”๋“ค ์—ญ์‹œ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ์šฐ ๋„ค ๋ฐฉํ–ฅ์— ๋‹ค๋ฅธ ๋ฐฐ์ถ”๊ฐ€ ์œ„์น˜ํ•œ ๊ฒฝ์šฐ์— ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

ํ•œ๋‚˜๊ฐ€ ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋Š” ๋•…์€ ๊ณ ๋ฅด์ง€ ๋ชปํ•ด์„œ ๋ฐฐ์ถ”๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์‹ฌ์–ด ๋†“์•˜๋‹ค. ๋ฐฐ์ถ”๋“ค์ด ๋ชจ์—ฌ์žˆ๋Š” ๊ณณ์—๋Š” ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋งŒ ์žˆ์œผ๋ฉด ๋˜๋ฏ€๋กœ ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๋ฐฐ์ถ”๋“ค์ด ๋ช‡ ๊ตฐ๋ฐ์— ํผ์ ธ์žˆ๋Š”์ง€ ์กฐ์‚ฌํ•˜๋ฉด ์ด ๋ช‡ ๋งˆ๋ฆฌ์˜ ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•œ์ง€ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฐ์ถ”๋ฐญ์ด ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉด ์ตœ์†Œ 5๋งˆ๋ฆฌ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค. 0์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ์ง€ ์•Š์€ ๋•…์ด๊ณ , 1์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ๋•…์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ ๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ์ฒซ์งธ ์ค„์—๋Š” ๋ฐฐ์ถ”๋ฅผ ์‹ฌ์€ ๋ฐฐ์ถ”๋ฐญ์˜ ๊ฐ€๋กœ๊ธธ์ด M(1 ≤ M ≤ 50)๊ณผ ์„ธ๋กœ๊ธธ์ด N(1 ≤ N ≤ 50), ๊ทธ๋ฆฌ๊ณ  ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ์œ„์น˜์˜ ๊ฐœ์ˆ˜ K(1 ≤ K ≤ 2500)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ K์ค„์—๋Š” ๋ฐฐ์ถ”์˜ ์œ„์น˜ X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘ ๋ฐฐ์ถ”์˜ ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด ๋งˆ๋ฆฌ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.


 

์‹ค๋ฒ„2

๋‹จ์ˆœํ•œ bfs ๋ฌธ์ œ์ด๊ธด ํ•œ๋ฐ,,, ์ข€ ๋”๋Ÿฝ์Šต๋‹ˆ๋‹ค

์™œ๋ƒ๋ฉด x์™€ y๊ฐ€ ๋ฐ˜๋Œ€๊ฑฐ๋“ ์š” ^^

์ž…๋ ฅ๋ฐ›์„๋•Œ ๊ทธ๋ƒฅ ๋ฐ˜๋Œ€๋กœ ๋ฐ›๋Š”๊ฒŒ ์ œ์ผ ๊ฐ„๋‹จํ•œ๋“ฏ

 

 

๋‚˜์˜ ํ’€์ด

#include <iostream>
#include <queue>
using namespace std;

int m;
int n;
int k;
int visited[50][50];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool canGo(int map[50][50],int x, int y){
    if(x<0 || y<0 || x>=n ||y>=m) return false;
    if(map[x][y] == 0) return false;
    if(visited[x][y]) return false;
    return true;
}

void bfs(int map[50][50], int x, int y){
    queue<pair<int, int>> q;

    q.push({x, y});
    visited[x][y] = 1;

    while(!q.empty()){
        pair<int, int> a = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i){
            int nx = a.first + dx[i];
            int ny = a.second + dy[i];
            if(canGo(map, nx, ny)){
                visited[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}

int main(){
    int t;
    cin >> t;

    int x, y;
    for (int i = 0; i < t; ++i){
        int cnt = 0;
        int map[50][50] = {0,};
        cin >> m >> n >> k;
        for (int j = 0; j < k; ++j){
            cin >> y >> x;
            map[x][y] = 1;
        }
        for (int j = 0; j < n;++j){
            for (int h = 0; h < m; ++h){
                if (map[j][h] == 1 && visited[j][h] == 0){
                    bfs(map, j, h);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";

        for (int j = 0; j < n;++j){
            for (int h = 0; h < m; ++h){
                visited[j][h] = 0;
            }
        }
    }
}

 

728x90