[백준 알고리즘] 1743번 음식물 피하기

문제 

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

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

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

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

입력

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

출력은 음식물 중 가장 큰 음식물의 크기이다

풀이

음식물들이 근처에 있는 것끼리 뭉친다는 것은 하나의 컴포넌트를 만든다는 말 같다 하나의 컴포넌트 안에 가장 많은 vertex를 포함하는 경우를 찾아야겠다 한번 DFS가 시작될 때 마다 각 컴포넌트의 수를 센다 근데 일단 input 이 바로 그래프로 들어오는게 아니고 행렬의 일부 좌표가 들어오기때문에 그래프로 만들어주는 부분도 같이 해주면되겠다

근데 만들었던 DFS쓸려니까 행렬로 들어오는 input을 쓰기엔 비효율적인거같아서 전에 풀었던 유기농배추처럼 풀어봐야겠다

코드는 유기농배추에서 cnt++만 추가해줘서 가장 큰 cnt를 출력해주면된다

* n, m 헷갈려서 반대로 썼다가 몇번 틀리고 맞았습니다 받았다 ㅠㅠ