[BaekJoon 1743번] 음식물 피하기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1743번: 음식물 피하기

 

 

[문제 설명]

 

 

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

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

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

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

 

 

[입력]

 

 

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

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
3 4 5 3 2 2 2 3 1 2 3 1 1	4

 

 

[힌트]

 

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

 

 

[문제 풀이]

 

 

음식물이 떨어진 좌표를 받을 때 탐색을 할 통로[음식물 떨어진 x좌표 - 1][음식물 떨어진 y좌표 - 1] = 1로 저장했다.

( -1을 한 이유는 배열은 0부터 시작되기 때문이다)

 

그리고 시작점을 찾기 위해 2중 for문을 이용해 시작점을 찾고 BFS 알고리즘을 사용했다.

그리고 음식물의 크기는 큐에서 pop하는 횟수라고 알 수 있다.

그래서 max 함수를 이용하여 시작점을 찾고 음식물의 크기를 구할 때마다 가장 큰 값을 찾을 수 있도록 했다.

 

그리고 이문제는 백준 1926번 그림 문제와 유사하다.

[BaekJoon 1926번] 그림(C++)

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

int board[101][101];
bool visited[101][101];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int answer = 0;
    int N, M, K; // 세로, 가로, 음식물쓰레기 개수
    cin >> N >> M >> K;
    for(int i = 0; i < N; ++i) {
        fill(board[i], board[i] + M, 0);
        fill(visited[i], visited[i] + M, false);
    }

    for(int i = 0; i < K; ++i) {
        int r, c;
        cin >> r >> c;
        board[r-1][c-1] = 1; // 음식물인 경우 1로 표시
    }
    
    queue<pair<int, int>> q;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < M; ++j) {
            if(visited[i][j] || board[i][j] == 0) continue;
            // 음식물일 때만 확인
            q.push({i,j});
            visited[i][j] = true;
            int cnt = 0;
            while(!q.empty()) {
                pair<int, int> cur = q.front();
                q.pop();
                cnt += 1;
                for(int k = 0; k < 4; ++k) {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if(visited[nx][ny] || board[nx][ny] == 0) continue;
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
            answer = max(answer, cnt);
        }
    }
    cout << answer;
}