[백준] 1743번 음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

 

나는 이 문제를 bfs로 풀었다. dfs로도 풀수 있을 것 같은데...

나는 dfs보다 bfs가 더 편하다고 느꼈기 때문에 bfs를 선택하였다.

dfs로도 풀 수 있어야 하는데...

나는 제일 먼저 

인풋을 받았다. 문제를 풀때 가장 먼저 하는 행동이다. 

그리고 나서 받은 정보들을 이중 배열에 넣었다. 근데 이중 배열에 넣을때 무조건 1로만 넣게 하였다.

왜냐하면 여러가지 숫자를 넣게 되면 햇갈리수 있기 때문이다. 

만든 그래프가 양방향이 아니라고 예상했기 때문에 단방향으로 만들었다.

즉,

a[0][1] = a[1][0] = 0이런식으로 동작하지 않게 했다는 뜻이다.

그리고 그 값들을 bfs돌렸다.

중요한 사실이 있다. 처음에는 이동경로로 계산을 하였지만 그렇게 계산하다보니

한쪽으로 값이 증가되는 현상을 막을 수 는없었다.

여기서 이동경로라 함은 move[nx][ny] = move[x][y]+1 이런식으로 전 이동 경로에서 1을 더한값을 계속 주입해주는 형태다. 왜 이렇게 하면 안되는 이유는

오른쪽으로 5만큼가고 왼쪽으로 2만큼갔다고 생각해보자(본문의 내용과 어느정도 관련만 있습니다.)

즉,     5 4 3 2 1 0 1 2 

그러면 총 거리는 8이 된다. 근데 이동 경로로 계산하게 되면 전체 거리를 계산할 수 없게 된다. 왜냐하면 1과 2라는 숫자가 겹치게 되는데 이걸 딱히 계산할 방법이 없기 때문이다.

여기에는 2가지 방법이 있다.

첫 번째 방법은 이 방법으로 한뒤, 0이상의 값들의 갯수를 세는 방법이 있고,

두 번째 방법은 이동경로로 구하는 것이 아닌 count 변수를 만들어 그곳에 계속해서 더해주는 방식이 있다.

나는 이중에서 두 번째 방법을 선택했다.

왜냐하면 어떤 범위가 더 큰지 물어보는 문제인데 첫 번째 방법으로는 이것을 계산하기에 마땅하지 않았기 때문에 사용하지 않았다. 

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int arr[200][200];
bool vist[200][200];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
vector<int> sizes;
void bfs(int x,int y) {
  int count = 1;
  vist[x][y] = true;
  queue<pair<int, int>> q;
  q.push({x,y});

  while(!q.empty()) {
  int xx =  q.front().first;
  int yy = q.front().second;
  q.pop();
  for(int i = 0; i<4;i++) {
    int nx = dx[i] + xx;
    int ny = dy[i] + yy;
    if (nx < 0 || n <= nx || ny < 0 || m <= ny) continue;
    if (vist[nx][ny]) continue;
    if (arr[nx][ny] == 0) continue;
    vist[nx][ny] = true;
    q.push({nx,ny});
    count++;
  }
}
sizes.push_back(count);
}
int main() {
  cin >> n >> m >> k;

  while(k--) {
    int x,y;
    cin >> x >> y;
    arr[x-1][y-1] = 1;
  }
   
  for(int i = 0;i<n;i++) {
    for(int j = 0; j<m;j++) {
        if(arr[i][j] == 1 && !vist[i][j]) {
          bfs(i,j);
        }
    }
  }
  int mx = -1;
  for(int i : sizes) {
    if (mx < i) {
      mx = i;
    }
  }

  cout << mx;

}

 

* -1을 하는 이유는 문제에서 1부터 동작하는데 나는 0부터 동작하는 편이 더 나을거라 생각해서 -1을 했다.

 

#include <bits/stdc++.h>
#define endl "\n"
#define int long long
  
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;

int n, m, k;
vvi board(101, vi(101));

vi dr = {-1,1,0,0};
vi dc = {0,0,-1,1};

int dfs(int r, int c) {
  if (board[r][c] == 0) return 0;
  int cnt = 1;
  board[r][c] = 0;
  for (int i=0; i<4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];
    if (nr < 1 || nr > n) continue;
    if (nc < 1 || nc > m) continue;
    if (board[nr][nc] == 0) continue;
    cnt += dfs(nr,nc);
  }
  return cnt;
}

signed main() {
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  #endif
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr); 

  cin >> n >> m >> k;
  for (int i=0; i<k; i++) {
    int r, c;
    cin >> r >> c;
    board[r][c] = 1;
  }

  int ans = 0;

  for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++) {
      ans = max(ans,dfs(i,j));
    } 
  }

  cout << ans << endl;

  return 0;
}

(dfs.v)