[C++] BOJ 2667 / BFS (문자열 파싱 접근)

문제 분석

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

BFS로 탐색하며 각 그룹의 개수를 계산하여 오름차순으로 정렬하여 출력하는 문제이다.

예제 입력 1

예제로 주어진 입력을 보면 다른 문제와는 다르게 "문자열"로 주어진 것을 알 수 있다. 이에 주의하여 입력을 처리해야 한다.

 

해결 방법

한자리 숫자의 문자는 '0'을 빼주면 ascii 코드로 계산되어 숫자로 변환된다. 이를 응용하여 입력 받으면 된다.

 

코드

#include <iostream>
#include <stdio.h>
#include <queue>
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define X first
#define Y second
int board[25][25];
int vis[25][25];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int>> q;
    vector<int> v;
    int n, k, area=0, cnt=0;
    string str;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> str;
        for(int j=0;j<n;j++) {
            board[i][j] = str[j] - '0';	// 문자를 숫자로 변환
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(vis[i][j] != 0 || board[i][j] == 0) continue;
            q.push({i,j});
            vis[i][j] = 1;
            while(!q.empty()) {
                pair<int,int> cur = q.front();
                q.pop();
                cnt++;
                for(int dir=0;dir<4;dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(vis[nx][ny] != 0 || board[nx][ny] == 0) continue;
                    q.push({nx,ny});
                    vis[nx][ny]=1;
                }
            }
            area++;
            v.push_back(cnt);
            cnt=0;
        }
    }
    sort(v.begin(), v.end());
    cout << area << "\n";
    for (auto e : v)
        cout << e << "\n";
}

 

풀이 복습

입력을 받을 때, getline을 사용해서 받아야 한다는 어처구니 없는 판단을 하여서 시간을 낭비했다.

getline과 cin의 차이를 앞으로는 햇갈리지 않기 위해 정리한다.

 

cin은 공백과 줄바꿈 "이전 까지"입력을 받고, getline은 공백과 줄바꿈을 포함하여 입력 받는다.

getline을 언제써야 하는지 정확한 감이 잡히지 않는다면, 4949번 문제를 보면 된다.

getline 사용법은 아래와 같다.

while(1) {
	getline(cin, str);
	if(str[0] == '.') break;
}

'.'이 나올 때 까지 입력받는다는 의미이다.