[백준] 1743번 음식물 피하기

문제

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

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

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

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

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

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

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제 입력 1

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1

4

힌트

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

내 코드

from collections import deque

DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 상하좌우

def bfs(matrix, start_x, start_y):
    q = deque([(start_x, start_y)])
    matrix[start_y][start_x] = 0  # 방문처리
    counts = 1

    while q:
        x, y = q.popleft()
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and matrix[ny][nx] == 1:
                matrix[ny][nx] = 0  # 방문처리
                q.append((nx, ny))
                counts += 1  # 음식물 1 증가

    return counts

N, M, K = map(int, input().split())
matrix = [[0] * M for _ in range(N)]  # 음식물 없음 0, 있음 1
max_counts = 0

for _ in range(K):
    r, c = map(int, input().split())
    matrix[r - 1][c - 1] = 1

for y in range(N):
    for x in range(M):
        if matrix[y][x] == 1:
            counts = bfs(matrix, x, y)
            max_counts = counts if counts > max_counts else max_counts

print(max_counts)

chatGPT

개선 코드

from collections import deque

# 상하좌우 방향 정의
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def bfs(matrix, start_x, start_y):
    queue = deque([(start_x, start_y)])
    matrix[start_y][start_x] = 0  # 방문 처리
    size = 1

    while queue:
        x, y = queue.popleft()
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and matrix[ny][nx] == 1:
                matrix[ny][nx] = 0  # 방문 처리
                queue.append((nx, ny))
                size += 1  # 음식물 크기 증가

    return size

# 입력 처리
N, M, K = map(int, input().split())
matrix = [[0] * M for _ in range(N)]

for _ in range(K):
    r, c = map(int, input().split())
    matrix[r - 1][c - 1] = 1

# BFS를 통해 최대 음식물 크기 찾기
max_size = 0

for y in range(N):
    for x in range(M):
        if matrix[y][x] == 1:
            max_size = max(max_size, bfs(matrix, x, y))

print(max_size)

---

새로운 개선사항

1. max 함수 활용으로 가독성 향상
   • 기존 코드에서 max_counts = counts if counts > max_counts else max_counts를 사용하는 대신, 파이썬의 max 함수를 활용했습니다.
   • max_size = max(max_size, bfs(matrix, x, y))로 간결하게 표현할 수 있어 가독성이 증가합니다.
2. counts → size로 변수명 변경
   • size는 음식물 크기를 직관적으로 나타내는 변수명으로, 의미를 더 명확히 했습니다.

부가 질문

내 생각

1. max 함수를 활용하자.