[백준] 음식물 피하기 (Python)

문제

코레스코 콘도미니엄 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가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

문제 정리

# 8층 - 3끼 식사 해결 공간
# 비양심적인 학생들로 음식물이 통로 중간 떨어져있음
# 그것들이 합쳐지면 큰 음식물 쓰레기
# 그 음식물 중 제일 큰 음식물 피해가는 문제
# ============================
# N 세로, M 가로 길이, K 음식물 쓰레기 개수
# 그 다음 K개의줄에 음식물 떨어진 좌표(r,c)
# r은 위에서 c는 왼쪽에서부터가 기준
# 붙어있는 음식물은 하나로 인식하고 크기는 +1씩해준다(4개가 붙으면 4)
# 대각선으로는 붙을 수 없고 상하좌우만 붙을 수 있음
# ===========================
# 1. 일단 data로 입력 값 다 뽑아오기
# 2. 첫째줄 N, M, K int화 시켜서 만들기
# 3. K만큼 반복 시켜서 음식물 좌표 담기
# 3-1. N,M 크기만큼의 배열 만들기(안에는 음... False 넣기)
# 4. x,y좌표값 넣을 deque 만들기(초기 값 0,0넣기)
# 5. deque가 남아있을때까지 while문 만들기
# 5-1. 상하좌우 directions 배열 만들기

결국 상하좌우로 움직일때마다 count를 +1시켜서, 그 쓰레기의 크기가 가장 큰 것을 확인해서 출력하는 문제라고 보면 된다.

코드 구현

import sys
from collections import deque

# 1.
input = sys.stdin.read
data = input().split()

# 2.
N, M, K = int(data[0]), int(data[1]), int(data[2])

# 3-1.
visit_space = [[False]*M for _ in range(N)]

# 3.
trash_position = [[0]*M for _ in range(N)]
index = 3

for _ in range(K):
  x, y = int(data[index]), int(data[index+1])
  trash_position[x-1][y-1]=1
  index += 2

def bfs(start_x,start_y):
  # 4.
  queue = deque([(start_x,start_y)])
  count = 1
  directions = [(-1,0),(1,0),(0,-1),(0,1)]
  # 5.
  while queue:
    x, y = queue.popleft()
    # 5-1.
    for dx, dy in directions:
      nx, ny = x+dx, y+dy
      if 0 <= nx < N and 0 <= ny < M and not visit_space[nx][ny] and trash_position[nx][ny] == 1:
        visit_space[nx][ny] = True
        queue.append((nx,ny))
        count += 1
  return count
  
max_trash_size = 0
visit_space = [[False]*M for _ in range(N)] # 초기화
for i in range(N):
  for j in range(M):
    if trash_position[i][j] == 1 and not visit_space[i][j]:
      max_trash_size = max(max_trash_size, bfs(i,j))
      
print(max_trash_size)

import sys
from collections import deque

# 1.
input = sys.stdin.read
data = input().split()

일단 한번에 입력 값 data에 넣기

# 2. 화면의 세로 크기 N, 가로 크기 M, 쓰레기의 개수 K
N, M, K = int(data[0]), int(data[1]), int(data[2])

N,M,K에 대해 정수화시키기

# 3. 음식물 쓰레기 위치와 방문 여부를 기록할 리스트
trash_position = [[0]*M for _ in range(N)]
index = 3
for _ in range(K):
    x, y = int(data[index]), int(data[index+1])
    trash_position[x-1][y-1] = 1  # 음식물 위치 기록
    index += 2

trash_position에 기본값 0을 넣어서 1을 넣는게 쓰레기 x,y좌표값이라고 생각
근데 실제로는 인덱스가 -1씩 해줘야 원하는 (x,y)좌표에 쓰레기가 있다고 인식시킬 수 있음

# BFS 함수 정의
def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    visit_space[start_x][start_y] = True
    count = 1  # 현재 시작 위치도 포함
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and not visit_space[nx][ny] and trash_position[nx][ny] == 1:
                visit_space[nx][ny] = True
                queue.append((nx, ny))
                count += 1
    return count

초기 값 (start_x,start_y)를 담는 deque를 선언해줌
visit_space는 외부에서 선언, 전역 변수로 취급해서 아래에서 선언해도 사용 가능, 함수 안 기준에서는 전역 변수 위치가 크게 중요하진 않음
그리고 방문하면 True로 바꿔줄 것이기 때문에 x,y값에 접근하면 True로 바로 전환
그리고 크기를 세야하므로 count는 1부터 시작
나머지는 BFS방식

# 4. 메인 루프: 음식물 위치에서 BFS를 실행하여 최대 덩어리 크기 계산
max_trash_size = 0
visit_space = [[False]*M for _ in range(N)]  # 방문 여부 초기화
for i in range(N):
    for j in range(M):
        if trash_position[i][j] == 1 and not visit_space[i][j]:
            max_trash_size = max(max_trash_size, bfs(i, j))

print(max_trash_size)

여기 부분이 이해가 잘 안갔었는데,
1이 나오는 값이 아닌 부분도 분명 탐색을 할텐데, 그러면 0이후의 1의 값도 방문을 하기때문에 visit_space가 True가 되지 않을까? 생각했는데,
다시 생각해보면, 상하좌우를 다 비교해도 0으로 감싸진다면, queue.append가 진행되지 않으므로, popleft도 안되고 애초에 queue가 비어서 while문이 종료된다.
그러다 결국 0인곳을 for문에서 접근하면 어차피 if문때문에 bfs함수가 실행되지 않고, 그렇게 여러 쓰레기가 나왔다면, 그 중에 가장 큰 쓰레기의 크기를 구하기 위해 max까지 사용!!

와 이게 이해는 되도, 정말 사소하거나 디테일한 부분까지는 구현하기 너무 어렵다 ㅠㅠ