백준 1743번: 음식물 피하기

BOJ

백준 1743번: 음식물 피하기

문제

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

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

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

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

접근

입력
세로길이(N) 가로길이(M) 음식물개수(K)
좌표(r, c)

음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물이 된다. 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

결국은, 가장 큰 음식물을 찾으면 된다. 생각보다 쉽다.
bfs와 dfs 두 방법 모두 이용할 수 있는 거 같다. 이번에는 dfs를 이용했으니 다음에는 bfs를 이용해서 풀어야겠다.

# dfs 함수
def dfs(y, x, cnt):

    forest[y][x] = 0

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

        if 1 <= ny <= N and 1 <= nx <= M:
            if forest[ny][nx] == 1:
                cnt = dfs(ny, nx, cnt + 1)

    return cnt

dfs 함수를 만들 때 cnt 매개변수를 쓰고 싶지 않았는데, 다른 방법이 딱히 생각이 나지 않았다.

Correct Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(y, x, cnt):
    forest[y][x] = 0

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

        if 1 <= ny <= N and 1 <= nx <= M:
            if forest[ny][nx] == 1:
                cnt = dfs(ny, nx, cnt + 1)

    return cnt


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

for i in range(K):
    r, c = map(int, input().split())

    forest[r][c] = 1

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

answer = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if forest[i][j] == 1:
            answer = max(answer, dfs(i, j, 1))

print(answer)

참고 사이트