[백준(BOJ)] 11123번 : 양 한마리... 양 두마리... - C++[CPP]

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

11123번: 양 한마리... 양 두마리...

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

char 값으로 받은 데이터를 0과 1로 변환하여 int arr에 넣고 bfs 함수를 만들어줬다.

 

그리고 한 바퀴가 다 끝나서 queue를 탈출시 count up을 해주고 마지막에 저장된

count 값을 출력한 후, 배열과 방문 기록을 초기화 한 다음 T만큼 돌려주는 로직을 짰다!

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 101

int T, H, W;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
queue<pair<int, int>> q;

void bfs(int a, int b) { //bfs
    visited[a][b] = true;
    q.push({a,b});
    while(!q.empty()) {
        a = q.front().first;
        b = q.front().second;
        q.pop();
        for(int i=0;i<4;i++) {
            int na = a + dx[i];
            int nb = b + dy[i];
            if(na >= 0 && nb >=0 && H>na && W>nb) {
                if(!visited[na][nb] && arr[na][nb]) {
                    q.push({na,nb});
                    visited[na][nb]=true;
                }
            }
        }
    }
}
//초기화
void reset() {
    for(int i=0;i<MAX;i++) {
        for(int j=0;j<MAX;j++) {
            arr[i][j] = 0;
            visited[i][j] = false;
        }
    }
}

int main() {
    cin >> T;

    while(T--) { // T만큼 반복
        int cnt = 0;
        cin >> H >> W;
        //배열에 0과 1로 저장
        for(int i=0;i<H;i++) {
            for(int j=0;j<W;j++) {
                char x;
                cin >> x;
                if(x == '.') arr[i][j] = 0;
                else arr[i][j] = 1;
            }
        }
        //bfs가 한바퀴 끝날 때마다 count up!
        for(int i=0;i<H;i++) {
            for(int j=0;j<W;j++) {
                if(arr[i][j] && !visited[i][j]) {
                    bfs(i,j);
                    cnt++;
                }
            }
        }
        //결과 출력
        cout << cnt << "\n";
        reset(); //초기화
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!