1743 음식물 피하기

💡문제 분석 요약

• 이전에 풀었던 단지 번호붙이기 문제와 거의 유사했다.
• 한마디로 음식물이 뭉쳐져있으면 커지고, 제일 크게 커진 음식물 크기를 구하는 문제였다.
• 이는 DFS, BFS로 탐색하여 해당 구역에 1이 몇개 있는지 구하는 맥락이다.

💡알고리즘 설계

• BFS, DFS 모두 가능하다.

💡코드

import sys
sys.setrecursionlimit(10 ** 6)


n, m, k = map(int, input().split())
graph = [[0] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]

foods = []  # 음쓰들
foodWaste = 0  # 음쓰

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(k):
    r, c = map(int, input().split())
    graph[r - 1][c - 1] = 1  # 음식물 표시

def DFS(x, y):
    global foodWaste
    foodWaste += 1
    graph[x][y] = 0 # 현재지점 방문

    # 그래프에 덮어 씌워도 되는 상황이면 visited 안써도 됨.

    # DFS(visited 쓸 수 있음) : 군집화 -> 방문했던 곳을 또 다시 방문하지 않음.
    # BFS(visited 안써도 됨) : 거리, 초단위 가장 짧은 시간, 방문했던 곳을 또 방문할 수도 있음. (그래프는 검증용, 누적 가능)
    # 방문 했던 곳을, 또 방문하지 않기 위해서 visited 쓰는 것임.

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 내고, 음쓰가 있는 곳이라면
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
            DFS(nx, ny) # 해당 좌표로 이동


for i in range(n):
    for j in range(m):
        if (graph[i][j] == 1): # 음쓰가 있으면 DFS 실행
            DFS(i, j)
            foods.append(foodWaste) # 음쓰들 모아놓음
            foodWaste = 0  # 음쓰 초기화

print(max(foods))

💡시간복잡도

• 모든 정점을 확인하므로 O(n*m)이 될 것이다.

💡 틀린 이유

• 그래프 초기화할 때, 0,0 부터 시작하느냐 1,1부터 시작하느냐를 따져야하는데 이를 확인하지 않아서 틀렸다.

💡 틀린 부분 수정 or 다른 풀이

• (1,1)부터 시작하는 정점이므로(?) N*M개의 그래프에 대해서 정점 초기화시 인덱스에서 -1씩 더해주고 초기화해준다.

💡 느낀점 or 기억할정보

• DFS(visited 쓸 수 있음) : 군집화 -> 방문했던 곳을 또 다시 방문하지 않음.
• BFS(visited 안써도 됨, 쓸 수도 있음) : 거리, 초단위 가장 짧은 시간, 방문했던 곳을 또 방문할 수도 있음. (그래프는 검증용, 누적 가능)
• 방문 했던 곳을, 또 방문하지 않기 위해서 visited 쓰는 것임.