[python] 백준 > DFS/BFS > 음식물 피하기(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]

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y):
    q = deque()
    cnt = 1
    q.append((x, y))
    cnt = set()
    while q:
        qx, qy = q.popleft()
        cnt.add((qx, qy))
        if (qx, qy) in visited:
            continue
        visited.add((qx, qy))
        for i in range(4):
            sx, sy = qx+dx[i], qy+dy[i]
            if not(0<=sx<N and 0<=sy<M):
                continue
            if arr[sx][sy] == arr[qx][qy]:
                q.append((sx, sy))
    return len(cnt)

if __name__ == '__main__':
    N, M, RC = map(int, input().split())
    arr = [[0]*M for _ in range(N)]
    for _ in range(RC):
        r, c = map(int, input().split())
        arr[r-1][c-1] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    visited = set()
    answer = []

    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0 and (i, j) not in visited:
                count = bfs(i, j)
                answer.append(count)
    print(max(answer))

• 빈 곳에는 0, 쓰레기가 있는 곳엔1을 넣었다.
• bfs를 사용하여 1끼리 모여있는 것들의 갯수를 구한뒤 최댓값을 출력했다.

[다른 사람의 풀이 - DFS]

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n, m, k = map(int, input().split())
trash = {tuple(map(int, input().split())) for _ in range(k)}
dy, dx = [-1, 1, 0, 0], [0, 0, 1, -1]
check = [[False]*(m+1) for _ in range(n+1)]
def dfs(start):
    y, x = start
    global count
    count += 1
    for i in range(4):
        b, a = y+dy[i], x+dx[i]
        if 1<=b<=n and 1<=a<=m and (b, a) in trash and check[b][a]==False:
            check[b][a] = True
            dfs((b,a))
result = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        if (i,j) in trash and check[i][j]==False:
            count = 0
            check[i][j]=True
            dfs((i,j))
            result = max(count, result)
print(result)

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N,M,T = map(int,input().split())
graph=[ [0]*M for _ in range(N)]
result=[]
for _ in range(T):
    a,b=map(int,input().split())
    graph[a-1][b-1]=1
def dfs(x,y):
    global size
    if x<0 or x>=N or y<0 or y>=M:return False
    if graph[x][y]==0:return False
    if graph[x][y]==1:
        graph[x][y]=0
        size+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False
for i in range(N):
    for j in range(M):
        size=0
        if dfs(i,j):result.append(size)
print(max(result))