백준 알고리즘 1743. 음식물 피하기

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

전체 코드

김시은님 코드

n, m, k = map(int, input().split())

# 0이 빈곳이고 1이 쓰레기가 있는 곳으로 설정
# index를 1부터 사용하기 위해 n+1, m+1로 설정
graph = [[0] * (m + 1) for _ in range(n + 1)]

# 쓰레기가 있는 곳의 좌표를 입력 받아 그래프에 1을 삽입
for _ in range(k):
    x, y = map(int, input().split())
    graph[x][y] = 1

# 쓰레기 크기 반환 함수 정의 
def dfs(x, y):

    # graph 범위를 벗어나면 0 반환
    if x <= 0 or x > n or y <= 0 or y > m:
        return 0
    
    # 쓰레기가 해당 위치에 있다면 
    if graph[x][y] == 1:
        # 해당 위치를 방문 처리
        graph[x][y] = 0
        # 현재 위치 + 상하좌우 쓰레기 개수 모두 합하여 반환
        return 1 + dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1)
    
    return 0

max_size = 0

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if graph[i][j] == 1:
            # 모든 위치에서 DFS를 실행하여 가장 큰 쓰레기 더미의 크기를 찾음
            max_size = max(max_size, dfs(i, j))

print(max_size)

 

dfs의 상하좌우 함수의 리턴값을 통해 쓰레기 개수를 구하는 방법이 상당히 깔끔한 것 같다. matrix에서 개수를 카운트할 때 해당 코드를 외워두면 유용할 것 같다.

내가 풀이한 코드

import sys

sys.setrecursionlimit(100000)
max_count = 0
count = 0


def solution(mat):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    w = len(mat[0])
    h = len(mat)

    def dfs(mat, x, y, w, h):
        global max_count
        global count
        if 0 <= x < w and 0 <= y < h and mat[y][x] == 1:
            mat[y][x] = 0
            count += 1
            for i in range(len(dx)):
                dfs(mat, x + dx[i], y + dy[i], w, h)

    global max_count
    global count
    for y in range(h):
        for x in range(w):
            if mat[y][x] == 1:
                count = 0
                dfs(mat, x, y, w, h)
                max_count = max(max_count, count)

    return max_count


N, M, K = map(int, input().split())
mat = [[0] * M for _ in range(N)]

for _ in range(K):
    y, x = map(int, sys.stdin.readline().split())
    mat[y - 1][x - 1] = 1

print(solution(mat))

 

DFS 진행 시 전역변수가 과도하게 많이 사용된다. 가능한 위의 코드처럼 재귀함수의 리턴을 활용하는 방법을 연습한다.