[파이썬] 백준 9347 : 울타리 (골드3)

[파이썬] 백준 9347 : 울타리 (골드3)

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

---

문제

준규는 화원을 운영중이다. 준규는 엄청난 가치를 지닌 대마꽃를 M개의 행과 N개의 열을 가진 토지에 경작하는데 진욱이가 자꾸 훔쳐가서 고민에 빠졌다. 준규는 진욱이가 훔쳐가지 못하게 꽃 주변을 울타리로 둘러쌓다. 하지만 시간이 지나면서 울타리 몇개가 부서졌다. 진욱이는 이때를 틈타 다시 꽃을 훔지려고 한다.

아래 보이는 그림은 11행 12열의 화원을 나타낸다. 0은 울타리가 없거나 꽃이 심어져 있는 부분을 나타내고 1은 울타리가 있는 곳을 나타낸다. 화원에 들어 오려면 노란색 부분부터 들어와야 한다.

진욱이가 꽃을 훔치러 화원에 들어왔다. 울타리를 요리조리 피해서 들어가는데 이때 상, 하, 좌, 우로 밖에 이동할 수 없다. 진욱이는 파괴적 성향을 지니고 있기 때문에 울타리로 가로막혀 더이상 안으로 접근할 수 없을 때 울타리를 부순다. 진욱이가 되도록 적은 수의 울타리를 부수면서 안으로 들어갈때, 최대한 많이 울타리를 부순 횟수와 , 그때 얻을 수 있는 꽃의 수를 구하여라.

입력

첫째 줄에 테스트 케이스의 수 T (≤ 10) 가 주어진다. 같은 줄에 주어지는 여러개의 정수는 공백으로 구분된다.

각각의 테스트 케이스의 첫째 줄에는 두개의 정수 R, C가 주어진다 (5 ≤ R, C ≤ 1 000)

R은 화원의 행을 나타내고 C는 열의 수를 나타낸다.

두 번째 줄부터 R+1번째 줄까지 화원의 정보가 주어진다. 화원은 꽃이 심어질 수 있는 부분인 0 과 울타리가 설치된 1로 이루어져 있다.

화원에는 적어도 하나 이상의 꽃이 심어지는 부분이 있다고 가정한다.

출력

각각의 테스트 케이스에 대해서 2개의 정수를 출력한다. 첫 번째 정수는 진욱이가 부수는 최대 울타리의 수이고, 두 번째 정수는 그때 얻을 수 있는 꽃의 최대 개수이다. 두 개의 정수는 공백으로 구분한다.

---

풀이

0. 방향성 생각

• 가장 많이 부수고 들어가야 하는 영역의 넓이들 중 최대 영역의 넓이를 구한다.
• 문제의 번역이 이상한건지 모르겠는데, 가장 많이 부수고 들어가야 하는 영역이 가장 넓은 영역의 넓이를 구하는 게 아니다.
• 가장 많이 부수고 들어가야 하는 영역들의 넓이의 합을 구하는 것.
• 발문이 조금 이상한데, 정답 코드와 비교해서 보니 영역의 합을 구한다.
• 다익스트라를 돌려서 visit 배열에 부수어야하는 울타리 수의 최솟값을 기록한다.
• 0-1 너비우선이든, 다익스트라든 array의 크기가 약간은 크기 때문에 큐나 힙에 더미 데이터가 들어가는 것을 방지하면 좋다.
  

1. import, 전역 변수 설정

from collections import deque,defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

dire = [(1,0),(-1,0),(0,1),(0,-1)]
inf = 1e9

• 4방향 이동 방향 정의
• 다익스트라 배열 초기화를 위한 inf 정의
  

2. 입력

for _ in range(int(input())):

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

    visit = [[inf]*X for _ in range(Y)]
    inside = lambda x,y : 0<=x<X and 0<=y<Y

    heap = []
    for y in (0,Y-1):
        for x in range(X):
            crash = arr[y][x]
            hq.heappush(heap,(crash,x,y))
            visit[y][x] = crash
    for x in (0,X-1):
        for y in range(Y):
            crash = arr[y][x]
            hq.heappush(heap,(crash,x,y))
            visit[y][x] = crash

• visit에 inf로 초기화를 시킨다.
• inside로 범위 밖에 나가지 않게 설정해준다.
• 힙에는 테두리를 모두 추가한다.
• arr값이 1인 경우 부수고 들어간 경우이고, 0인 경우는 부수지 않고 들어간 경우이다.
• crash로 부순 유무를 int로 저장해서 힙에 추가.
  

3. 다익스트라

    while heap:
        t,x,y = hq.heappop(heap)

        for dx,dy in dire:
            nt,nx,ny = t+1,x+dx,y+dy
            if inside(nx,ny):
                if arr[ny][nx] and nt < visit[ny][nx]:
                    visit[ny][nx] = nt
                    hq.heappush(heap,(nt,nx,ny))
                elif not arr[ny][nx] and t < visit[ny][nx]:
                    visit[ny][nx] = t
                    hq.heappush(heap,(t,nx,ny))

• 위에서 시작 시 많은 양의 데이터를 주었기 때문에, 미리 방문한 영역보다 큰 t를 가지면 더미 데이터를 제거할 수 있다.
• 울타리를 부수고 들어가고 갱신할 수 있는 경우에는 nt = t+1을 힙에 추가한다.
• 그렇지 않은 경우에는 t 그대로 추가한다.
  

4. 출력

    dist = dd(int)
    for y in range(Y):
        for x in range(X):
            if not arr[y][x]:
                dist[visit[y][x]] += 1
    answer = list(sorted(dist.items()))
    print(*answer[-1])

• array를 훑으면서 부순 울타리별 영역 넓이를 구한다.
• dict의 items를 가져오고 정렬하면 리스트의 맨 뒤에는 울타리를 가장 많이 부수어야 하는 영역의 넓이가 들어있다.
  

---

전체코드

from collections import deque,defaultdict as dd
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

dire = [(1,0),(-1,0),(0,1),(0,-1)]
inf = 1e9

for _ in range(int(input())):

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

    visit = [[inf]*X for _ in range(Y)]
    inside = lambda x,y : 0<=x<X and 0<=y<Y

    heap = []
    for y in (0,Y-1):
        for x in range(X):
            crash = arr[y][x]
            hq.heappush(heap,(crash,x,y))
            visit[y][x] = crash
    for x in (0,X-1):
        for y in range(Y):
            crash = arr[y][x]
            hq.heappush(heap,(crash,x,y))
            visit[y][x] = crash

    while heap:
        t,x,y = hq.heappop(heap)

        if t > visit[y][x]:
            continue

        for dx,dy in dire:
            nt,nx,ny = t+1,x+dx,y+dy
            if inside(nx,ny):
                if arr[ny][nx] and nt < visit[ny][nx]:
                    visit[ny][nx] = nt
                    hq.heappush(heap,(nt,nx,ny))
                elif not arr[ny][nx] and t < visit[ny][nx]:
                    visit[ny][nx] = t
                    hq.heappush(heap,(t,nx,ny))

    dist = dd(int)
    for y in range(Y):
        for x in range(X):
            if not arr[y][x]:
                dist[visit[y][x]] += 1
    answer = list(sorted(dist.items()))
    print(*answer[-1])

코멘트

• 사람들이 많이 안 푼 문제들은 데이터 오류가 많다...
• 조건문, 변수 변경 시 실수하지 않도록 체크 잘 하기.