백준 2667. 단지번호붙이기 [실패]

1.실패 원인

처음에 bfs라고 생각했다. '1'인 배열으로부터 이웃한 값들중 1을 찾아서 하나로 묶을 생각을 했다. 작성 도중에 재귀를 이용하지 않고 bfs를 작성하는 방법이 헷갈려 다음 좌표를 찾는 알고리즘과 bfs 알고리즘이 서로 다른 방향으로 동작해 끝까지 문제를 풀지 못했다. 

 

2.작성 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dx[4] = { 0, 1, 0, -1};
int dy[4] = { -1, 0, 1, 0};
string arr[25];
bool vi[25][25] = { false, };
int N, cnt;
vector <int> ans;

void dfs(int i, int j) {
  
  vi[i][j] = true;
  cnt++;
  int k; 
  
  for (k = 0; k < 4; k++) {
    int newY = i + dy[k];
    int newX = j + dx[k];

    if (0 <= newX && newX < N && 0 <= newY && newY < N)
      if(arr[newY][newX] == '1' && !vi[newY][newX]) dfs(newY, newX);
  }
}

int main() {
  int i, j;

  cin >> N;

  for (i = 0; i < N; i++) cin >> arr[i];

  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      if (arr[i][j] == '1' && !vi[i][j]) {
        cnt = 0;
        dfs(i, j);
        ans.push_back(cnt);
      }
    }
  }

  sort(ans.begin(), ans.end());
  
  cout << ans.size() << endl;
  for (i = 0; i < ans.size(); i++) cout << ans[i] << endl;

  return 0;
}

3.참고 코드

https://sihyungyou.github.io/baekjoon-2667/

백준 2667번 : 단지번호붙이기

 

 

4. 해결 방안

이번 문제는 dfs,bfs 모든 방법으로 풀수있다고 한다. 

문제점을 짚어보자면 쓸데없이 개발용 코드를 작성하고 있었다는 점. 위의 링크를 보면 알겠지만..

코드가 굉장히 단순하다. 이해하기도 쉽고.. 정말 작성이 잘돼있었다.

그리고, 괜찮다고 생각한 아이디어는 좌표를 이동하는 방식이었다. 내가 작성했던 코드는 위치에 따라서

4가지 방향을 다 검사한 후 그 결과를 구조체형식으로 반환하는 방법을 사용했는데 sihyungyou님은

이웃한 좌표로 이동할 때 증가량을 x,y 구분하여 배열로 만들어 놓은후 그저 더하기만 했다.

초기조건과 dfs 함수 자체가 정말 깔끔해서 이해하기가 쉬웠다.

 

일단 가장 큰 문제점은 해당 문제를 어떻게 접근해야 할지, 무슨 도구를 써야할지 감이 안잡힌다는 것이다.

dfs는 익숙해졌지만 bfs는 돌아서니 또 까먹은듯하다. 반복을 통해 체득하는 방법밖에는 없을 것 같다.