[파이썬] 백준 1736 : 쓰레기 치우기 (골드1)

[파이썬] 백준 1736 : 쓰레기 치우기 (골드1)

• https://www.acmicpc.net/problem/1736
  

---

문제

방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레기를 로봇을 사용해서 수거하려고 하는데, 로봇은 왼쪽 위에서 출발해 오른쪽 아래로 도착한다. 즉, 로봇은 현재 위치에서 오른쪽, 혹은 아래쪽으로밖에 이동할 수 없다.

이때, 모든 쓰레기를 수거하기 위해서 필요한 최소 로봇의 수를 출력하는 프로그램을 작성하시오.

입력

첫 행에는 N, M이 공백으로 구분되어 주어진다.

다음 N 행에 걸쳐 M 개의 수가 주어진다. 이 값이 0이면 해당하는 위치가 비어 있다는 뜻이고, 1이면 해당하는 위치에 쓰레기가 있음을 뜻한다.

출력

필요한 최소 로봇의 수를 출력한다.

---

풀이

0. 방향성 생각

• $N=100$이고 array 크기가 $100^2 = 10000$이라서 $N^4$ 이하로 접근한다.
• 오른쪽, 아래쪽으로만 이동이 가능하다.
• (x,y)에서 쓰레기를 주웠으면 (x,y)좌표보다 같거나 큰 위치의 쓰레기만 주울 수 있다.
• 문제 예시에서는, 맨 위, 중앙, 아래 3그룹으로 나누어서 주으면 3번에 쓰레기를 치울 수 있다.
  

1. 입력

from collections import deque
import sys

input = lambda :sys.stdin.readline().rstrip()

Y,X = map(int,input().split())
arr = [tuple(map(int,input().split())) for _ in range(Y)]

trash = [(x,y) for y in range(Y) for x in range(X) if arr[y][x]]
trash = deque(trash)

• Y를 기준으로 삼고, 오른쪽으로 순회하면서 쓰레기의 좌표를 덱에 담는다.

2. 출력

answer = 0
while trash:
    x,y = trash.popleft() # 가장 먼저 발견하는 쓰레기
    answer += 1
    temp = set() # 다음 만날 쓰레기들을 저장
    for idx,(nx,ny) in enumerate(trash):
        if x<=nx and y<=ny:
            x,y = nx,ny
            temp.add(idx)
    trash = deque(trash[i] for i in range(len(trash)) if i not in temp)
print(answer)

• 가장 먼저 발견하는 쓰레기의 좌표를 (x,y)로 둔다.
• 주웠던 쓰레기를 기억하기 위해 set에 저장한다.
• trash에서 나오는 쓰레기들을 보면서 기준 (x,y)보다 좌표가 같거나 큰 경우에 (x,y)를 발견한 쓰레기 위치인 (nx,ny)의 좌표로 업데이트 한다.

---

전체코드

from collections import deque
import sys

input = lambda :sys.stdin.readline().rstrip()

Y,X = map(int,input().split())
arr = [tuple(map(int,input().split())) for _ in range(Y)]

trash = [(x,y) for y in range(Y) for x in range(X) if arr[y][x]]
trash = deque(trash)

answer = 0
while trash:
    x,y = trash.popleft()
    answer += 1
    temp = set()
    for idx,(nx,ny) in enumerate(trash):
        if x<=nx and y<=ny:
            x,y = nx,ny
            temp.add(idx)
    trash = deque(trash[i] for i in range(len(trash)) if i not in temp)
print(answer)

코멘트

• 2차원으로 바뀌었을 뿐, 1차원으로 flatten 시키면 $1<=N<10000$인 문제라서 $O(N^2)$로 풀이.
• 2차원 array를 1차원으로 flatten 하는 과정에서 쓰레기만 추출하면 $O(N^2)$를 많이 줄일 수 있다고 생각했는데, 큰 차이가 없는 듯 하다.