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

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

그리드 위에 양들을 '#'으로 표현했고, 그리드 위에 몇 개의 양 무리가 있는지 세는 문제다. 상하좌우로 인접한 양을 하나의 무리로 취급한다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 0 ≤ T ≤ 100
• 1 ≤ H, W ≤ 100

 

많아도 100 × 100 × 100번 안에 풀 수 있는 문제 ?

 

격자 안에 무리를 세는 문제는 보통 bfs로 많이 푼다. 그리드 정보를 입력 받을 때 string으로 받고 하나씩 떼어내야 한다는 것만 고려하면 될 것 같다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. T와 H,W, 그리드 정보 입력 받기
2. 이중 반복문을 돌려 방문하지 않은 '#'인 곳에서 bfs 함수 돌리기
   1. bfs 함수를 돌 때 그리드에 방문했다는 걸 표시
3. bfs 함수를 돌린 횟수 출력

 

테스트 케이스마다 정답과 그리드, 방문 정보를 초기화해야 한다.

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define pii pair<int,int>

int t,h,w,board[100][100],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool visit[100][100];

void bfs(int a, int b) {
    queue<pii> q;
    q.push({a,b});
    visit[a][b] = true;
    while (!q.empty()) {
        auto [x,y] = q.front();
        q.pop();
        for (int i=0; i<4; i++) {
            int cx=x+dx[i],cy=y+dy[i];
            if (cx<0 || cx>=h || cy<0 || cy>=w || visit[cx][cy] || board[cx][cy]==0) continue;
            q.push({cx,cy});
            visit[cx][cy] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> t;
    while (t--) {
        int ans=0;
        string str;
        fill(&board[0][0],&board[100][0],0);
        fill(&visit[0][0],&visit[100][0],false);
        cin >> h >> w;
        for (int i=0; i<h; i++) {
            cin >> str;
            for (int j=0; j<w; j++) {
                board[i][j] = (str[j]=='#'? 1 : 0);
            }
        }

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (board[i][j]==1 && !visit[i][j]) {
                    bfs(i,j);
                    ans++;
                }
            }
        }

        cout << ans << '\n';
    }
}