#2667 단지번호붙이기 (C++)

링크 : www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

이 문제는 먼저 유의 사항을 파악해야하는데,

입력값이 다닥다닥 붙어있으며, 입력 값을 굳이 int형 숫자라고 명시하지 않았다는 점이다. 

코드를 구현하고 답을 체크할때, 이상하게 프로세스가 제대로 종료되지 못하는 현상이 발생할 수 있다. 

만약 테스트 케이스가 다음과 같이 공백을 두고 입력되었다면 문제가 없었을 것이다.

고안해본 해결책은 다음과 같다. 

 

(1) 문자열로 값을 입력 받는다. 이렇게 해서 입력 값은 단 1byte, 즉, 한 자리의 값만 받게 된다.

(2) 해당 문자 - 48로써 배열에 값을 넣는다. 문자값 - 48은 해당 문자의 숫자로 변경된다.

(아스키 코드 설명 : astrid-dm.tistory.com/18)

  

문제 풀이는 다음과 같다.

 

(1) 배열의 첫 번째부터 for문을 시작하며, 해당 위치를 방문한 적이 없고(false), 해당 위치의 값이 '1'이면 dfs를 시작한다.

(2) dfs를 시작하면서 해당 위치는 방문한 적이 있음으로(true) 변경하고 집의 갯수를 +1 한다.

(3) 해당 위치의 위 아래 좌 우 방향으로 방문한 적이 없고(false) 위치의 값이 '1'이면 다시 dfs를 시작한다. 

(4) 최종적으로 dfs를 종료할 때, 전체 단지의 갯수를 +1 해주며 집의 갯수는 0으로 초기화해준다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0, arr[25][25], res = 0, cnt=0, y2=0,x2=0;
bool check[25][25] = {false,};
int ym[4] = {1,0,-1,0}; //시계방향으로 주택의 위치 파악
int xm[4] = {0,1,0,-1};
vector<int> v;
char c;

bool track(int y, int x){
    if(y>=n||x>=n||y<0||x<0) return false;
    if(check[y][x]||arr[y][x]==0) return false;
    return true;
}

void dfs(int y, int x){
    cnt++;
    check[y][x]=true;
    for(int i=0; i<4; i++){
        y2=y+ym[i];
        x2=x+xm[i];
        if(track(y2,x2)==true) dfs(y2,x2);
    }
    return;
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> c;
            arr[i][j] = c-48; // 주의! 문자를 숫자형으로 변경해주었다.
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(check[i][j]==false&&arr[i][j]==1){
                cnt = 0;
                dfs(i,j);
                res++;
                v.push_back(cnt);
            }
        }
    }
    cout << res << "\n";
    if(!v.size()==0){
        sort(v.begin(), v.end());
        for(int i=0; i<v.size(); i++) cout << v[i] << "\n";
    }

    return 0;
}

처음에는 무식하게 테스트 케이스의 숫자들을 한 칸씩 서로 거리를 두며 (마치 사회적 거리두기처럼) 테스트 케이스를 체크했었다.

이렇게 할 경우, visual studio code 내에서는 정답이 나왔지만 백준 내에서는 반복적으로 오답이 나왔다. 

 

무언가 내가 놓친 점을 파악하고, 백준의 테스트 케이스 자체를 넣어도 문제되지 않게끔 코드를 다시 구현했다.