알고리즘(C++) / 백준 1743 : 음식물 피하기

1743

boj.kr/1743

1743번: 음식물 피하기

 

문제

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

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

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

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

 

입력

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

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

 

출력

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

 

코드

//1743 음식물 피하기
#include <iostream>
using namespace std;
int N, M, K;
bool trash[102][102] = { false, };
bool visited[102][102] = { false, };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
int maxsize = 0;
int s = 0; //size

void DFS(int x, int y) {
    visited[x][y] = true;
    s++;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > N || ny > M)
            continue;
        if (visited[nx][ny] == false && trash[nx][ny] == true) {
            DFS(nx, ny);
        }
    }
}

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

    cin >> N >> M >> K;

    int r, c;
    for (int i = 0; i < K; i++) {
        cin >> r >> c;
        trash[r][c] = true;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (trash[i][j] == true && visited[i][j] == false) {
                s = 0;
                DFS(i, j);
                if (maxsize < s) {
                    maxsize = s;
                }
            }
        }
    }
    cout << maxsize << "\n";

    return 0;
}

 

설명

기본적인 DFS 문제이다. 

쓰레기를 bool 형으로 쓰레기가 존재한다면 true, 존재하지 않는다면 false로 저장할 수 있다.

반복문으로 trash 배열을 방문하여 true이고 전에 방문하지 않았다면 DFS, 깊이 우선 탐색으로 탐색한다. 노드를 하나씩 방문할 때마다 size를 저장하는 s를 1씩 증가시켜 인접해있는 노드들의 크기를 구하고, maxsize를 구현할 수 있다. 

 

결과

 

고찰

전에 풀었던 DFS 문제와 비슷한 유형이었다.

출력할 때 maxsize가 아닌 그냥 s를 출력해줘서 게속 틀리게 되었다......

이것도 모르고 한 30분 이상은 고민한거 같다.... 멍청... 구현할 때... 꼼꼼하게 구현... 하기...!!

 

난이도

●○○○○