[Google Kick Start] 2021 구글 킥스타트 Round A Rabbit house 풀이

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

BFS를 사용하면 된다. 핵심은 상자가 많은 칸의 주변을 먼저 채워준다는 것이다. 이를 위해 우선순위 큐를 사용하였다. 생각해보면 상자의 갯수는 계속해서 바뀔 수 있다. arr = [2,0,4]에서 0번째 인덱스부터 탐색할 경우 1번째 인덱스의 수는 1이 될 것이다. 최소수를 구해야하므로. 그런데 다시 2번째 인덱스의 4를 보면 1번째 인덱스는 다시금 3으로 수정되어야 하는 경우가 발생한다.

이같은 경우가 생기는 이유는 작은 수를 큰 수보다 먼저 탐색했기 때문이다. 따라서 우선순위 큐를 사용해 상자의 갯수가 큰 칸을 기준으로 먼저 탐색해주면 된다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14

import heapq

import copy 
D = ((1,0),(-1,0),(0,1),(0,-1))
T = int(input())
for t in range(T):
    arr = []
    r, c = map(int, input().split())
    for i in range(r):
        temp = list(map(int, input().split()))
        arr.append(temp)
    q = []
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0:
                heapq.heappush(q, (-arr[i][j], (i,j)))
    visit = [[0 for _ in range(c)] for _ in range(r)]
    result = copy.deepcopy(arr)
    while q:
        element = heapq.heappop(q)
        value, x, y = -element[0], element[1][0], element[1][1]
        if visit[x][y] != 1:
            visit[x][y] = 1
            for dx, dy in D:
                nx, ny = x+dx, y+dy
                if 0<=nx<=r-1 and 0<=ny<=c-1 and visit[nx][ny] == 0:
                    result[nx][ny] = max(result[nx][ny], value-1)
                    heapq.heappush(q, (-result[nx][ny], (nx,ny)))
    cnt = 0
    for i in range(r):
        for j in range(c):
            cnt += result[i][j] - arr[i][j]
    print(f"Case #{t+1}: " + str(cnt))