난이도

Silver 1

풀이 참고 유무

X

막힌 부분

X

문제

문제 바로가기

코레스코 콘도미니엄 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

문제 검토

최단경로가 아니라 전부 탐색만 하면 되기 떄문에 BFS,DFS 둘 다 좋은 방법이다.

풀이(python)

Python

r,c,n=map(int,input().split())
stage=[[0 for _ in range(c)] for _ in range(r) ]

for x in range(n):
    a,b = map(int,input().split())
    stage[a-1][b-1]=1

from collections import deque
def BFS(row,col):
    q = deque()
    q.append((row,col))
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    cnt=1
    
    while q:
        currow,curcol = q.popleft()
        for mv in range(4):
            nrow=currow+dx[mv]
            ncol=curcol+dy[mv]
            if nrow<0 or nrow>=r or ncol<0 or ncol>=c:
                continue
            if stage[nrow][ncol]!=1:
                continue
            q.append((nrow,ncol))
            stage[nrow][ncol]=0
            cnt+=1
            
    return cnt
res=0
for x in range(r):
    for y in range(c):
        if stage[x][y]==1:
            stage[x][y]=0
            cur=BFS(x,y)                        
            if cur>res:
                res=cur                
print(res)    

BFS를 진행하고 큐에 append할 때마다 count 해준다.
쓰레기 한 개의 크기 탐색이 끝나면 카운트를 리턴해줘서 크기를 비교하며 가장 큰 쓰레기를 찾는다.

걸린 시간

26:05

총평

일반적인 BFS만 사용하면 바로 풀리는 문제인데 자잘한 오타와 실수 때문에 시간이 생각보다 많이 지체된다.
실수를 줄여보자