[baekjoon] 백준 1743번(파이썬): 음식물 피하기

문제

1743번: 음식물 피하기

- 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다.

- 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다.

- 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

- 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

- 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 

- 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

- 좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

- 음식물 중 가장 큰 음식물의 크기를 출력하라.

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 탐색을 하면서 쓰레기를 찾으면 카운트하고 연결된 모든 노드를 탐색하면 쓰레기를 뭉쳐준다.

- 뭉쳐준 쓰레기 중에서 제일 큰 쓰레기의 크기를 출력한다.

코드

import sys
sys.setrecursionlimit(10**6) # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x > n or y <= -1 or y > m:

        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:

        # 쓰레기 카운트
        cnt.append(1)

        # 해당 노드 방문 처리
        graph[x][y] = 0
        
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return True
    return False


# 테스트 케이스만큼 반복

n, m, k = map(int, sys.stdin.readline().split())

# 각 노드가 연결된 정보를 표현
graph = [[0] * (m + 1) for i in range(n + 1)]

# 2차원 리스트의 맵 정보를 입력 받는다.
for i in range(k):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1

res = [] # 뭉친 쓰레기 리스트
cnt = [] # 쓰레기 카운트 리스트

# 현재 위치에서 DFS 수행
for i in range(n + 1):
    for j in range(m + 1):

        if dfs(i, j):
            # 뭉친 쓰레기를 리스트에 추가
            res.append(len(cnt))
            cnt = []

# 뭉친 쓰레기 중에 제일 큰 쓰레기를 출력
print(max(res))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법